1004. 最大连续1的个数III

淩亂°似流年 2022-10-31 00:46 182阅读 0赞

##### 题目描述： #####

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长（连续）子数组的长度。

##### 示例 1： #####

输入：A = [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： #####

输入：A = [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.  1 <= A.length <= 20000
2.  0 <= K <= A.length
3.  A\[i\] 为 0 或 1

##### 题解： #####

**滑动窗口算法**

滑动窗口中用到了左右两个指针，它们移动的思路是：以右指针作为驱动，拖着左指针向前走。右指针每次只移动一步，而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间。

**代码**

/** * @param {number[]} A * @param {number} K * @return {number} */
    var longestOnes = function(A, K) { 
        let left = 0, right = 0, count = 0, sum = 0
        while (right < A.length) { 
            if(A[right] === 0) { 
                count ++ // 统计0的个数
            }
            right ++  // 移动右端点
            while (count > K) { 
                if(A[left] === 0) { 
                    count --
                }
                left ++ // 移动左端点
            }
            sum = Math.max(sum, right - left)
        }
        return sum
    };