每日算法系列【LeetCode 1004】最大连续1的个数 III

题目描述

给定一个由若干 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]
A[5] 和 A[10] 从 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]
A[4] 、A[5] 和 A[9] 从 0 翻转到 1，最长的子数组长度为 10。

提示

• 1 <= A.length <= 20000
• 0 <= K <= A.length
• A[i] 为 0 或 1

题解

这题可以采用滑动窗口方法来求解。也就是用头尾指针 l 和 r ，初始化都是 l = r = 0 ，然后向右移动指针 r 。用变量 cnt0 记录 [l, r] 区间内有几个 0 ，用 res 保存答案。

如果 A[r] = 0 ，那就 0 的数量 cnt0 加 1 。并且 0 的数量和 K 判断，如果 cnt0 <= K ，那就说明 [l, r] 中间的 0 不多，可以用至多 K 次机会填充，那就继续向右移动 r 。但是如果 cnt0 > K ，那就说明 0 的数量太多了，得删掉点 0 了，这时候就得向右移动 l 。这时候看情况，如果 A[l] = 0 ，就要减小 cnt0 ，直到 cnt0 <= K 为止，不再移动 l 。然后继续移动 r ，重复上面过程即可。过程中时刻更新最长的距离 res 。

因为 l 和 r 分别最多移动 n 次，所以最终的时间复杂度是  的。

那么为什么这样是正确的呢？不会漏掉正确答案所在的区间吗？我们看看漏掉的是哪些区间。对于一个固定的 r ，移动 l 直到 0 的数量小于等于 K （记为 l' ）的过程中，漏掉的是 [<l, r] 和 [>l', r] 这些区间。前者 0 数量太多，不符合题意；后者长度更小，显然不是答案。然后继续右移 r ，直到第一个 0 数量大于 K 的位置，漏掉了 [<l, >r] 和 [>l, >r] 区间。前者 0 的数量一定大于 K ，为什么呢？因为右端点在 r 的时候， l 已经是最靠左使得 0 数量小于等于 K 的位置了，而现在 r 向右移动了， l 更不可能左移了；后者长度更小，不予考虑。综上考虑，最优的区间一定被考虑充分了。

代码

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int n = A.size();
        int l = 0, r = 0, cnt0 = 0, res = 0;
        while (r < n) {
            if (!A[r]) {
                cnt0++;
                while (cnt0 > K && l <= r) {
                    if (!A[l++]) cnt0--;
                }
            }
            res = max(res, r - l + 1);
            r++;
        }
        return res;
    }