滑动窗口

2023-01-03

字数统计: 2.8k字 | 阅读时长: 11分

前言

滑动窗口算法的基本思想和一些实践。

滑动窗口算法（Sliding Window Algorithm）

Sliding window algorithm is used to perform required operation on specific window size of given large buffer or array.
滑动窗口算法是在给定特定窗口大小的数组或字符串上执行要求的操作。

This technique shows how a nested for loop in few problems can be converted to single for loop and hence reducing the time complexity.
该技术可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度。

滑动：表示窗口是移动的。

窗口：窗口的大小并不一定是固定的，可以不断扩容直到满足一定的条件；也可以不断缩小，直到找到一个满足条件的最小窗口；当然也可以是固定大小。

滑动窗口算法主要应用在数组类结构上（包括字符串），其思想可以用来解决一些 查找满足一定条件的连续区间的性质（如长度等）的问题。由于区间连续，因此当区间发生变化时，可以通过已有的计算结果对搜索空间进行剪枝，这样便减少了重复计算，降低了时间复杂度。

总之，滑动窗口法的核心思想就是利用已有计算结果减少重复计算，关键就是如何利用，所谓的滑动窗口只是其外在表现。

学习过计算机网络的读者应该对滑动窗口的模式并不陌生，而其他初次听说该思想的同学可能会一头雾水，下面我们通过一个简单的例子解释它。

例一：长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

暴力法

暴力法：双循环，每次依据一个开始位置寻找长度最小的符合条件子数组。

// author: SilenceZheng66
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int subLen = nums.length+1;
        for(int i=0;i<nums.length;i++){
            int sum = 0;
            int tmpSubLen = 0;
            int j = i;
            while(j<nums.length&&sum<target){
                sum += nums[j++];
                tmpSubLen++;
            }
            if(sum>=target&&tmpSubLen<subLen) subLen = tmpSubLen;
        }
        if(subLen<=nums.length) return subLen;
        else return 0; 
    }
}

最终超时，原因在于重复计算过多。时间复杂度$O(n^2)$。

滑动窗口

滑动窗口：通过左右指针划定窗口位置，指针由左向右滑动模拟窗口滑动，初始时左右指针重合指向索引0，而后右指针移动至第一个符合条件的位置（窗口内子数组符合条件），记录长度，此后左指针逐位移动，每次移动若窗口符合条件则再记录，直至窗口不符合条件，执行此左右移动过程直至右指针推出数组。

// author: SilenceZheng66
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // 滑动窗口
        int sum = 0, left = 0, right = 0, minSubLen = nums.length + 1;

        while(right<nums.length){
            // 寻找符合条件的最小窗口
            while(sum<target&&right<nums.length) sum+=nums[right++];
            // 缩小窗口直至不符合条件
            while(sum>=target){
                // 记录最小窗口大小
                if((right-left)<minSubLen&&sum>=target) minSubLen = right-left;
                sum-=nums[left++];
            }
        }

        if(minSubLen<=nums.length) return minSubLen;
        else return 0; 
    }
}

该算法的最终时间复杂度为$O(n)$，关于这个时间复杂度，可以想像数组中的每个元素至多被操作两次（右指针划过、左指针划过），因此操作数为 $2n$，即$O(n)$。被减少的运算就是各符合条件的窗口的交集。

该例中，窗口的大小是不固定的，事实上窗口的固定与否并不重要（固定窗口用单指针+长度即可），关键在于如何构造窗口并利用已有计算结果。现在我们已经了解了如何使用滑动窗口算法，下面进行更多实践来加深理解。

例二：尽可能使字符串相等

给你两个长度相同的字符串，s 和 t。

将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。

如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。

如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

采用滑动窗口解决，主要思路还是通过左右指针划定窗口位置，但要注意例二和例一的显著区别：例二求的是符合条件的最大长度，而例一求的是最小长度。在求解时，我们的滑动窗口通常都是由小至大进行扩张，求符合条件的最小子数组时，我们可以认为最初符合条件的窗口为符合条件的最小长度；而在求最大子数组时，只有当窗口内子数组初次不符合条件时，我们才能知道前一窗口为当前符合条件的最大窗口。

下面给出两种解法：

滑动窗口一

我写的滑动窗口法的思路是每次右指针都移动到初次不符合条件的位置，然后以右指针位置减去一表示真实符合条件的右指针位置。

// author: SilenceZheng66
class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int left = 0, right = 0, maxLen = 0, sum = 0;

        while(right<s.length()){
            // 移动右至符合条件
            while(right<s.length()&&sum<=maxCost) sum+=Math.abs(s.charAt(right)-t.charAt(right++));
            // 判断，由于求最大长所以不用每次移动左都判断
            // 在右指针推出的情况下窗口内数组可能不满足条件，故判断并修正
            if(right>=s.length()&&sum<=maxCost) maxLen = Math.max(maxLen, right-left);
            else maxLen = Math.max(maxLen, right-left-1);
            // 移动左至不符合条件
            // 注意sum==maxCost时不能移动，否则可能会错过最优解
            while(sum>maxCost) sum-=Math.abs(s.charAt(left)-t.charAt(left++));
        }
        
        return maxLen;
    }
}

这种写法看似思路简单，每一轮循环都想一次将右指针移到合适的位置，其实需要考虑的边界条件较多，如右指针推出但窗口不符合条件。另外，对于本题而言，有一共性问题需要注意，即左指针在sum==maxCost时不能继续移动，因为有可能出现窗口右侧s[i]==t[i]的情况。

滑动窗口二（思想来自[1]）

该写法的思想是每次右指针右移都附加判断和指针左移，这样一来就可以避免“右指针移动到初次不符合条件的位置”带来的问题。

// author: SilenceZheng66
class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int left = 0, right = 0, maxLen = 0, sum = 0;

        while(right<s.length()){
            // 移动右
            sum+=Math.abs(s.charAt(right)-t.charAt(right++));
            // 移动左
            while(sum>maxCost) sum-=Math.abs(s.charAt(left)-t.charAt(left++));
            // 判断
            maxLen = Math.max(maxLen, right-left);
        }

        return maxLen;
    }
}

可以看出，两种方法的窗口构造也不尽相同，笔者的方法是“真窗口存在于假窗口之中”。

例三：滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位

返回滑动窗口中的最大值。

这是一道固定窗口大小的题目，给出两种解法，分别是稍加记忆的暴力法和滑动窗口法，后者的速度是前者的40倍。本题其实更能体现出滑动窗口与暴力法的区别，即算法对于单一元素指针划过的次数。

稍加记忆的暴力法

选择使用左指针加偏移构造窗口，则暴力的求窗口内元素最值的方式为遍历窗口。窗口在移动的过程中，若最值仍位于窗口内，则只需比较新进入的元素和原始最值；若原始最值被排出，则需要重新选举最值。

// author: SilenceZheng66
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans = new int[nums.length-(k-1)];
        // offset = k-1
        int left = 0, max = Integer.MIN_VALUE, maxIndex = -1;

        while(left<ans.length){
            int right = left + (k-1);
            if(maxIndex>=left&&maxIndex<=right){
                if(nums[right]>=max){
                    max = nums[right];
                    maxIndex = right;
                }
            }
            else {
                int tmpMax = Integer.MIN_VALUE; 
                int tmpMaxIndex = maxIndex;
                for(int i = left; i <= right; i++){
                    // 取等于有利于减少最大值索引被排出的情况
                    if(nums[i]>=tmpMax){
                        tmpMax = nums[i];
                        tmpMaxIndex = i;
                    }
                }
                max = tmpMax;
                maxIndex = tmpMaxIndex;
            }
            ans[left++] = max;
        } 

        return ans;
    }
}

该方法在最优情况（原始最值永远不被排出，just fantasy）下可以取得不错的时间效率，但最坏情况下等同于暴力法，故属于效率较差的算法。

滑动窗口（思想来自[1]）

上一个方法没有利用好窗口内的计算结果，下面介绍一个更好的思路，该方法采用右指针构造窗口，核心思路在于维持一个队首最大的双端队列（这里用LinkedList代替）以保存最大值，可以设想数组逐步进入该队列，当数组中第一个窗口进入队列后，就开始对队首元素进行检验，若已经滑出窗口则出队。

// author: SilenceZheng66
class Solution {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int right = 0;
        int[] res = new int[nums.length - (k-1)];
        int index = 0;
        LinkedList<Integer> list = new LinkedList<>();

        while (right < nums.length) {
            // 维持list的首位为窗口中最大元素
            while (!list.isEmpty() && nums[right] > list.peekLast()) {
                list.removeLast();
            }
            // 不断添加
            list.addLast(nums[right++]);
            // 构造窗口完成，这时候需要根据条件做一些操作
            if (right >= k){
                res[index++]=list.peekFirst();
                // 若list首位已位于窗口外
                if(list.peekFirst() == nums[right-k]) {
                    list.removeFirst();
                }
            }
        }
        return res;
    }
}

由此可见，滑动窗口算法的核心思想在于如何表示窗口以及利用已有信息，有时窗口可能是抽象的。

参考文献

[1]https://www.cnblogs.com/huansky/p/13488234.html
[2]https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html

后记

首发于 silencezheng.top，转载请注明出处。