1004. Max Consecutive Ones III

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */

题目给我们一个只包含 0 或 1 的数字数组 nums 以及一个数字 k

要求我们计算最多可以反转 k 个 0 为 1 的情况下，最长且连续为 1 的子数组长度是多少

解题思路

这题的主要思路为滑动窗口，而且是不定长的滑动窗口

我们在构建滑动窗口的时候需要注意两点：

1. 窗口中不能含有超过 k 个 0
2. 窗口的左右边界必须是 0 或者数组边界（要包含所有可能的 1）

滑动窗口由两个阶段构成：

• 扩张：如果当前窗口 0 的个数小于 k，则可以持续扩张
• 收缩：如果当前窗口的 0 个数为 k 时，我们需要收缩窗口直到个数小于 k

最后我们需要一个变量记录最长的窗口长度

Javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestOnes = function (nums, k) {
    let res = 0
    let left = 0
    for (let right = 0; right < nums.length; right++) {
        while (nums[right] === 0 && k === 0) {
            if (nums[left] === 0) {
                k++
            }
            left++
        }
        if (nums[right] === 0 && k > 0) {
            k--
        }
        res = Math.max(res, right - left + 1)
    }

    return res
};