无妄，往吉

0%

Sliding Window

发表于 更新于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

滑动窗口（Sliding Window），顾名思义，即在数组/字符串设计一个左边界和一个右边界，从而获得一定长度的子元素，在此基础上，窗口随着边界的变化而滑动。其用于解决数组/字符串的子元素问题，它可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度。

我们可以通过一组题目来比较好的理解滑动窗口的应用：

485. 最大连续1的个数

给定一个二进制数组， 计算其中最大连续1的个数。

Simple Test Case
1
2
3
输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.

对于这道题，我们很容易能够想到暴力解决的办法，对数组内的元素遍历一次，设置变量count，逢1加1，逢0归0，最后得到最大的count。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int max_len = 0, count = 0;
        
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == 1) {
                count++;
                max_len = max(max_len, count);
            } else {
                count = 0;
            }
        }
        return max_len;
    }
};

那么，如果为其增加一个条件，比如可以最多将数组中的一个0翻转为1，那如何求最大长度呢？

487. 最大连续1的个数 II

给定一个二进制数组，你可以最多将 1 个 0 翻转为 1，找出其中最大连续 1 的个数。

Simple Test Case
1
2
3
输入：[1,0,1,1,0]
输出：4
解释：翻转第一个 0 可以得到最长的连续 1。当翻转以后，最大连续 1 的个数为 4。

这时，我们可以采取滑动窗口算法，计算窗口内元素1的数量，判断窗口大小 - 元素1的数量 > 1是否为真，如果其为真，那么说明窗口内部包含1个以上的0元素，需要收紧窗口，最后求最大窗口即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0;
        for (int count = 0, l = 0, r = 0; r < nums.size(); ++r) {
            if (nums[r] == 1) count++;
            
            while (r - l + 1 - count > 1) {
                if (nums[l++]) --count;
            }
            res = max(res, r - l + 1);
        }
        
        return res;
    }
};

如果放宽限制，我们可以最多将K个值从0翻转为1呢？

1004. 最大连续1的个数 III

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

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

Simple Test Cases
1
2
3
4
5
6
7
8
9
10
输入：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。
---------------
输入：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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int res = 0;
        for (int count = 0, l = 0, r = 0; r < A.size(); ++r) {
            if (A[r] == 1) count++;
            
            while (r - l + 1 - count > K) {
                if (A[l++]) --count;
            }
            res = max(res, r - l + 1);
        }
        
        return res;
    }
};