力扣1004-最大连续1的个数 Ⅲ

原题

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



示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。


提示：

1 <= nums.length <= 105
nums[i] 不是 0 就是 1
0 <= k <= nums.length

分析

1. 问题转换

可以翻转 k 个 0 后数组中最长的连续 1 的长度
👇
只能包含 k 个 0 的连续 1 的数组
👇
滑动窗口记录包含 k 个 0 的结果集，返回最长的结果集的长度

解题思路

1. 连续 + 最长 ==> 考虑滑动窗口
2. 翻转 k 个 0 为 1 得到连续 1 的最长长度 ==> "包含 k 个 0 的最长 1 组成的最长长度"
   • 一次遍历，遇到 1 右端扩张 r++
   • 遇到 0 记录 0 的个数
   • 一旦 0 的个数超过 k（count > k），收缩左边（收缩之前左端元素为 0，更新窗口中 0 的个数 - 1 ）
   • 每次移动右指针之后都记录当前窗口的长度（结果的子集）

伪代码

代码

for 循环

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestOnes = function (nums, k) {
  // 翻转 k 个 0 得到最长连续 1 的长度
  // 把最长连续1看作窗口，内部只能包含 <= k 个，否则窗口不合法（>k)，就需要收缩左区间
  // 直到内部0的个数 < k之前，都一直收缩左区间
  // 每次移动右指针都记录当前连续 1 的长度

  let l = 0
  let count = 0
  let len = 0
  for (let r = 0; r < nums.length; r++) {
    if (nums[r] == 0) {
      // 右指针遍历的时候遇到 0 就更新当前窗口中 0 的个数
      count++
    }
    while (count > k) {
      // 窗口中 0 的个数超过题目限制的 k ，收缩左区间确保窗口是合法的
      if (nums[l] == 0) count--
      // 右移左指针
      l++
    }
    // 每次移动右指针的时候，记录当前窗口的长度
    len = Math.max(r - l + 1, len)
  }
  return len
}

while 循环

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestOnes = function (nums, k) {
  // 翻转 k 个 0 得到最长连续 1 的长度
  // 把最长连续1看作窗口，内部只能包含 <= k 个，否则窗口不合法（>k)，就需要收缩左区间
  // 直到内部0的个数 < k之前，都一直收缩左区间
  // 每次移动右指针都记录当前连续 1 的长度

  let l = 0
  let r = 0
  let count = 0
  let len = 0
  while (r < nums.length) {
    // 遇到 0 更新 count
    if (nums[r] == 0) count++
    // 一旦 count > k 收缩左指针
    while (count > k) {
      // 收缩之前判断，即将被排除的元素是否为0，是则更新 count
      if (nums[l] == 0) count--
      l++
    }
    // 移动右指针之前记录当前区间的长度
    len = Math.max(len, r - l + 1)
    // 扩张右区间
    r++
  }
  console.log({ len })
  return len
}