usehook - 前端码易

code deep_

所有专栏

免费领 30 美元额度

创建时间: 2025-04-13最后更新: 2025-12-22作者: yangbo(96862973d)

NOTE

请勿第一时间看答案, 先自己思考, 思考不出来, 再看答案

题目描述

最大连续1的个数

给定一个二进制数组 nums 和一个整数 k, 假设最多可以翻转 k 个 0 , 则返回执行操作后, 数组中连续 1 的最大个数

测试用例

题目解析

二进制数只有 0 和 1, 所以 0 翻转之后, 就是 1. 因此, 翻转操作执行之后, 连续 1 的个数, 就是数组中部分已经存在的 1 的个数加上 0 的个数. 限制条件是：我们最多可以翻转 k 个 0.

我们可以定义一个滑动窗口, 来包含最多 k 个 0.

code.ts

1let left = 0
2let right = 0

此时我们需要开始移动 right 指针, 每次移动, 都有可能会有新的 0 进入到窗口. 因此, 我们需要统计窗口中 0 的个数, 并且记录窗口的最大宽度.

code.ts

1let max = 0;
2let zeroCount = 0;

此时的限制条件就是, 窗口中 0 的个数不能超过 k.

接下来我们让 right 指针依次移动, 直到超出了限制条件, 假定此时传入的 k = 2

超出之后, 我们需要移动 left 指针, 来减少窗口中, 0 的个数, 直到窗口中 0 的个数不超过 k.

code.ts

1// right 指针的移动过程中, 0 的个数超出了限制条件
2while (zeroCount > k) {
3  // 移动 left 指针直到满足限制条件
4  if (nums[left] === 0) {
5    zeroCount--;
6  }
7  left++
8}

然后再移动 right 指针, 重复上面的过程

最终完整代码如下

answer.ts

01export function longestOnes(nums: number[], k: number): number {
02  let left = 0;
03  let right = 0;
04  let max = 0;
05  let zeroCount = 0;
06
07  while(right < nums.length) {
08    if (nums[right] === 0) {
09      zeroCount++
10    }
11    
12    while (zeroCount > k) {
13      if (nums[left] === 0) {
14        zeroCount--
15      }
16      left++
17    }
18    
19    max = Math.max(max, right - left + 1)
20    right++
21  }
22  return max
23};

由于评论区已经有很多小伙伴在我写解题思路之前, 已经提前想到了这种限制条件的思路, 所以逼得我得换一个思路来解答.

刚好就有一个新的语义. 我们可以换个语义来描述限制条件, 由于最多只能有 k 个 0, 那么, 每有一个 0 进入到窗口, 我们就可以不用额外声明一个变量来记录 0 的个数, 而是直接减少 k 的值. 当 k < 0 的时候, 说明 0 的个数已经超了

所以代码可以稍微调整为如下

answer.ts

01export function longestOnes(nums: number[], k: number): number {
02  let max = 0;
03  let left = 0;
04  let right = 0;
05
06  while(right < nums.length) {
07    if (nums[right] === 0) {
08      k--
09    }
10    
11    while (k < 0) {
12      if (nums[left] === 0) {
13        k++
14      }
15      left++
16    }
17    max = Math.max(max, right - left + 1)
18    right++
19  }
20  return max
21};

由于少声明了一个变量, 所以后面这些写法有一些非常微弱的性能提升, 提供给大家参考学习.

原题地址：leetcode 1004

专栏首页

到顶

专栏目录