leetcode 1004.最大连续1的个数 III 滑动窗口

题目描述

最大连续1的个数 III
给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

---

思路

对于数组 A 的区间 $[left,right]$ 而言，只要它包含不超过 $k$ 个 $0$，我们就可以根据它构造出一段满足要求，并且长度为 $right-left+1$ 的区间。

因此，我们可以将该问题进行如下的转化，即：

对于任意的右端点 right，希望找到最小的左端点 left，使得 [left,right] 包含不超过 k 个 0。
只要我们枚举所有可能的右端点，将得到的区间的长度取最大值，即可得到答案。

要想快速判断一个区间内 0 的个数，我们可以考虑将数组 A 中的 0 变成 1，1 变成 0。此时，我们对数组 A求出前缀和，记为数组 P，那么[left,right] 中包含不超过 k 个 1（注意这里就不是 0 了），当且仅当二者的前缀和之差：
$P[right]-P[left-1]\le k$
$P[left-1]\ge P[right]-k$
我们继续观察上式，由于前缀和数组 P 是单调递增的，那么 上 式的右侧 P[right]−k 同样也是单调递增的。因此，我们可以发现：

随着 right 的增大，满足 上式的最小的 left 值是单调递增的。

这样一来，我们就可以使用滑动窗口来实时地维护 left 和 right 了。在 right 向右移动的过程中，我们同步移动left，直到 left 为首个（即最小的）满足 上式的位置，此时我们就可以使用此区间对答案进行更新了。

当我们使用滑动窗口代替二分查找解决本题时，就不需要显式地计算并保存出前缀和数组了。我们只需要知道 left 和 right 作为下标在前缀和数组中对应的值，因此我们只需要用两个变量 lsum 和rsum 记录 left 和right 分别对应的前缀和即可。

---

代码

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n=nums.size();
        int rsum=0,lsum=0,right,left=0;
        int res=-1;
        for(int right=0;right<n;right++)
        {
            rsum+=1-nums[right];
            while(lsum<rsum-k)
            {
                lsum+=1-nums[left];
                left++;
            }
            res=max(res,right-left+1);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---