滑动窗口

简介

介绍

滑动窗口算法（Sliding Window Algorithm）是一种用于解决数组或字符串相关问题的常用算法。它通过维护一个滑动窗口（窗口大小可变）在数组或字符串上移动，并根据问题的要求进行相应的操作。滑动窗口算法的核心思想是利用窗口的移动来优化问题的求解过程，避免不必要的重复计算，从而提高算法的效率。该算法通常用于解决需要在线性时间内找到满足特定条件的子数组或子字符串的问题。总结起来，滑动窗口算法是一种通过维护一个滑动窗口在数组或字符串上移动，并根据问题的要求进行操作的算法。它通过优化计算过程，提高了问题的求解效率。

滑动窗口算法的一般步骤：

1. 初始化窗口的起始位置和结束位置，可以是数组或字符串的开头或任意位置。
2. 根据问题的要求，确定窗口的大小和滑动规则。窗口的大小可以是固定的或可变的，滑动规则可以是逐步移动一个元素或直接跳过一部分元素。
3. 使用循环遍历数组或字符串，根据滑动规则逐步移动窗口，并在每个窗口位置上执行相应的操作(如判断条件、计算结果等)。
4. 根据问题的要求，更新结果或记录满足条件的子数组或子字符串。
5. 当窗口的结束位置达到数组或字符串的末尾时，算法结束。

算法关键

滑动窗口算法的关键在于确定窗口的起始位置、结束位置和滑动规则。通过合理地选择这些参数，可以有效地在线性时间内解决许多数组或字符串相关的问题。

注意事项

需要注意的是，滑动窗口算法并非适用于所有问题，但在一些特定情况下，它可以提供一种高效的解决方案。因此，在解决问题时，需要考虑是否可以应用滑动窗口算法来优化算法的性能。

通常用来解决的问题

子字符串匹配

连续子数组和

最小/最大子数组和

......

例题

最大连续1的个数

来源

例题链接：485 - 最大连续 1 的个数(LeetCode)

分析

分析题目不难看出可以用滑动窗口解决，其目的是找最大的个数，其中K是资源数，我们可以只扩大窗口或者平移窗口，而不去缩小窗口。其中是否是扩大还是平移与K有关，只要K大于0就可以扩大窗口，否则就平移窗口。

代码

class Solution {
    public int longestOnes(int[] A, int K) {
        int l = 0, r = 0;
        while (r < A.length) {
            if (A[r++] == 0) K--;
            if (K < 0 && A[l++] == 0) K++;
        }
        return r - l;
    }
}