usehook - 前端码易

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

题目描述

最大连续1的个数

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

测试用例

题目解析

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

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

1let left = 0
2let right = 0

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

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

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

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

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

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

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

最终完整代码如下

answer.ts

10export function longestOnes(nums: number[], k: number): number {
20  let left = 0;
30  let right = 0;
40  let max = 0;
50  let zeroCount = 0;
60
70  while(right < nums.length) {
80    if (nums[right] === 0) {
90      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

10export function longestOnes(nums: number[], k: number): number {
20  let max = 0;
30  let left = 0;
40  let right = 0;
50
60  while(right < nums.length) {
70    if (nums[right] === 0) {
80      k--
90    }
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

长度为 K 子数组中的最大和

二叉树的最大深度

专栏首页

到顶

专栏目录