跳转至

滑动窗口算法

每次遇到滑动窗口的算法题都写不出来或者不能用最好的方式写出来。这里总结一下。

从做题的技巧来说，滑动窗口算法技巧主要用来解决子数组问题，比如让你寻找符合某个条件的最长/最短子数组。如果要枚举所有的子数组，时间复杂度为\(O(n^2)\)，无论是枚举起始点+终止点，还是枚举长度+起始点。

// 枚举起始点+终止点
for (int i=0; i<n; i++) {
    for (int j=i+1; j<n; j++) {
        // v[i,j)
    }
}
// 枚举长度+起始点
for (int l=1; l<n; l++) {
    for (int i=0; i<n-l; i++) {
        // v[i, i+l)
    }
}

如果使用滑动窗口逻辑，来寻找最短/长子串则是：

// 最长，子串为[l,r)
int l=0; r=0;
while (r<n) {
    while (!ok(window)) {
        window.pop(v[l]);
        l++;
    }
    window.push(v[r]);
    r++;
    if (ok(window)) {
        update_best(l,r);
    }
}
// 最短，子串为[l,r)
int l=0, r=0;
while (r<n) {
    window.push(v[r]);
    r++;
    while (ok(window)) {
        update_best(l,r);
        window.pop(v[l]);
        l++;
    }
}

滑动窗口并不能枚举出所有的子串，但是一些题目可能并不需要穷举所有子串，就能找到题目想要的答案。滑动窗口的本质其实是贪心。例如题目要求寻找最短子串：

  1. 对于一个确定的l，如果[l,r)已经满足条件，那么我们就不需要再枚举[l,r+x)了。
  2. 对于一个确定的r，如果[l,r)满足条件，我们还可以试一试[l+x,r)。

类似的，如果题目要求寻找最长子串，那么

  1. 对于一个确定的r，如果[l,r)已经满足条件，那么我们就不需要再枚举[l+x,r)了；否则我们再试[l+x,r)。
  2. 对于一个确定的l，如果[l,r)满足条件，我们还可以试一试[l,r+x)。

例题

1004. 最大连续1的个数 III - 力扣（LeetCode） 将问题转化成求最多有k个0的最长子串，然后直接套用模板就可以解决这个问题。

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        zeros = 0
        l, r = 0, 0
        maxlen = 0

        while r < len(nums):
            while (zeros > k):
                if nums[l] == 0:
                    zeros -= 1
                l += 1
            if nums[r] == 0:
                zeros += 1
            r += 1
            if zeros <= k:
                maxlen = max(maxlen, r-l)
        return maxlen

参考链接