Mrli
别装作很努力,
因为结局不会陪你演戏。
Contacts:
QQ博客园

算法与数据结构——滑动窗口、尺取法

2022/04/11 数据结构
Word count: 3,596 | Reading time: 16min

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.该技术可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度。

基本概念

滑动窗口是一种基于双指针的一种思想，两个指针指向的元素之间形成一个窗口，可以看做是一种双指针方法的特例。

窗口的做法分为定长窗口和不定长窗口，有些人把涉及窗口移动的都统称为滑动窗口做法。而在此，我们进行进一步的细分：

  • 定长滑动窗口
  • 变长滑动窗口——尺取法

应用：

利用窗口的特性，可以用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。由于区间连续，因此当区间发生变化时，可以通过旧有的计算结果进行修改，从而对搜索空间进行剪枝，这样便减少了重复计算，降低了时间复杂度。

Q：那么，具体什么情况可以用滑动窗口来解决实际问题呢？

  1. 一般给出的数据结构是数组或者字符串
  2. 求取某个子串或者子序列最长最短等最值问题或者求某个目标值时
  3. 该问题本身可以通过暴力求解——★滑动窗口跟双指针一样，针对一些问题能降低时间复杂度。

核心思路

窗口的形成

在具体使用之前，我们知道窗口实际是两个指针之间形成的区域，那关键就是这两个指针是如何移动的。

《挑战程序设计竞赛》这本书中把滑动窗口叫做「虫取法」，这也非常生动形象。因为滑动窗口的两个指针移动的过程和虫子爬动的过程非常像：前脚(right指针)不动，把后脚(left指针)移动过来；后脚不动，把前脚向前移动。

滑动窗口中用到了左右两个指针，它们移动的思路是：以右指针作为驱动，拖着左指针向前走。右指针每次只移动一步，而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间。

为了得到符合要求的最长子数组的长度，应遵循以下两点原则：

  • 当 start 的值固定时，end 的值应尽可能大；
  • 当 end 的值固定时, start 的值应尽可能小。

模板的执行思想是：

  1. 定义两个指针 left 和 right 分别指向区间的开头和结尾，注意是闭区间；定义 sums 用来统计该区间内的各个字符出现次数；
  2. 第一重 while 循环是为了判断 right 指针的位置是否超出了数组边界；当 right 每次到了新位置，需要增加 right 指针的求和/计数 --> sum；
  3. 第二重 while 循环是让 left 指针向右移动到 [left, right] 区间符合题意的位置；当 left 每次移动到了新位置，需要减少 left 指针的求和/计数；
  4. 在第二重 while 循环之后，成功找到了一个符合题意的 [left, right] 区间，便跳出循环，更新题目要求最大的区间长度，即 res = max(res, right - left + 1)。
  5. right 指针每次向右移动一步，开始探索新的区间。

代码模板

变长窗口模板

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
# 滑动窗口模板
left,right = 0, (0 or 1)
ans = target = 0
while right < len(nums):
   根据 right 更新 target 值
   while 窗口内数据不满足要求
      # 1. 更新 target 值
      # 2. 收缩左边界 ==> 使得新窗口满足要求
      # or: 更新 ans： 窗口相关最小值，则在此更新
    # or: 更新 ans： 求窗口相关最大值，则在此更新
    更新right(移动右边界)
返回 ans

具象化的Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findSubArray(nums):
    N = len(nums) # 数组/字符串长度
    left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
    sums = 0 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数
    res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
    while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
        sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数
        while 区间[left, right]不符合题意：# 此时需要一直移动左指针，直至找到一个符合题意的区间
            sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
            left += 1 # 真正的移动左指针，注意顺序不能跟上面一行代码写反
        # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
        res = max(res, right - left + 1) # 需要更新结果
        right += 1 # 移动右指针，去探索新的区间
    return res

另一种模板：

(right++在前)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
string s, t;
    // 在 s 中寻找 t 的「最小覆盖子串」
    int left = 0, right = 0;
    string res = s;
    
    while(right < s.size()) {
        window.add(s[right]);
        right++;
        // 如果符合要求，说明窗口构造完成，移动 left 缩小窗口
        while (window 符合要求) {
            // 如果这个窗口的子串更短，则更新 res
            // or: ans更新位置
            res = minLen(res, window);
            window.remove(s[left]);
            left++;
        }
        // or: ans更新位置
    }
    return res;

固定长窗口模板：

right更新在第一层while最后，且while中没有if (right > k)类似的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int maxVowels(String s, int k) {
        int right = 0;
        int len = s.length();
        int maxAns = Integer.MIN_VALUE;
        int target = 0;
		// 初始构造定长窗口
        while (right < k) {
            // 更新这段初始化窗口中的 target 值
        }
		// ★更新 ans 值 maxAns = Math.max(maxAns, );
        
        // 让 right (有边界)
        while (right < len) {
            // 更新 target 值
            // 更新 ans 值 maxAns = Math.max(maxAns, );
            right ++;
        }
        return maxAns;
    }

    public int isVowel(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ? 1 : 0;
    }
}

另一种模板：

  • (right++在前) --> 这个是可以调整的，相应地修改if
  • 有if right > k的判断，即窗口是否已经构造完成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 固定窗口大小为 k
   string s;
   // 在 s 中寻找窗口大小为 k 时的所包含最大元音字母个数
   int  right = 0;
   while(right < s.size()) {
       window.add(s[right]);
       // 注：如果放最后，则下面的if改成 right > k
       right++;
       // 如果符合要求，说明窗口构造完成，
       if (right>=k) {
           // 这是已经是一个窗口了，根据条件做一些事情
          // ... 可以计算窗口最大值等 
           // 最后不要忘记把 right - k 位置元素从窗口里面移除
       }
   }
   return res;

可以发现此时不需要依赖 left 指针了。因为窗口固定所以其实就没必要使用left。可以直接通过 right 指针来控制窗口。

由于窗口是固定的，因此可以轻易获取到 left 的位置，此处 left = right - k，所以在第二层while中可以通过nums[right-k]来获得left位置得值，从而从窗口中删除。

注： 虽然提供了两种模板，但不要贪多，跟二分模板一样，只要记住一种就行了。

easy point:

  • 窗口的长度: right - left + 1，
  • 假设窗口长度为k，则窗口内容为[right-k+1, right-k+2, ..., right]，要被剔除的left的索引为right-k：固定长窗口的题目中，可以通过right位置找到left位置。

一起做几题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
    public int maxVowels(String s, int k) {
        int left = 0, right = 0;
        int len = s.length();
        int maxAns = Integer.MIN_VALUE;
        int ans = 0;
        char[] chars = {'a', 'e', 'i', 'u', 'o'};
        while (right - left + 1 <= k) {
            if (contains(chars, s.charAt(right))) {
                ans++;
            }
            right++;
        }
        maxAns = Math.max(maxAns, ans);

        while (right < len) {
            if (contains(chars, s.charAt(right))) {
                ans += 1;
            }
            // 被排除的是元音
            if (contains(chars, s.charAt(right - k))) {
                ans -= 1;
            }
            maxAns = Math.max(maxAns, ans);
            right++;
        }

        return maxAns;
    }

    private boolean contains(char chars[], char ch) {
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == ch) {
                return true;
            }
        }
        return false;
    }
}


// 更好的做法:
class Solution {
    public int maxVowels(String s, int k) {
        int right =0;
        int sum = 0;
        int max = 0;
        while (right < s.length()) {
            sum += isYuan(s.charAt(right)) ;
            right++;
            if (right >=k) {
                max = Math.max(max, sum);
                sum -= isYuan(s.charAt(right-k));
            }
        }
        return max;
    }
    public int isYuan(char s) {
        return s=='a' || s=='e' ||s=='i' ||s=='o' ||s=='u' ? 1:0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
   
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if (len <= 1) {
            return len;
        }

        int ans = 0;
        int left = 0, right = 0;
        HashSet<Character> set = new HashSet<>();
        while (right < len) {
            // 把删除之前s.charAt(right)位置内所有的字符
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left++));
            }
            set.add(s.charAt(right));
            ans = Math.max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
     public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0;

        int minLen = Integer.MAX_VALUE;
        int len = nums.length;
        int sum = 0;
        while ( right < len) {
            sum += nums[right];
            while (sum >= target) {
                // 由于需要求最小, 因此这边在left收缩过程中更新minVal
                minLen = Math.min(minLen, right - left +1);
                sum -= nums[left];
                left ++;
            }
            right ++;
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int longestOnes(int[] nums, int k) {
        int ans = 0;
        int left= 0, right = 0;
        int len = nums.length;
        int zeroTimes = 0;

        while (right < len) {
            int now = nums[right];
            // 把当前修改成1
            if (now == 0) {
                zeroTimes ++;
            }
            // 如果欠了k，则需要从左边进行挪动补偿；保证下一次添加nums[right]时 k一定非负
            while( zeroTimes > k) {
                if (nums[left] == 0) {
                    zeroTimes--;
                }
                left ++;
            }
            // 获得最大长度
            ans = Math.max(ans, right - left + 1);
            right ++;
        }

        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public double findMaxAverage(int[] nums, int k) {
      int i = 0;
      int sum = 0;
      while (i < k) {
          sum += nums[i++];
      }
      double maxV = -10000;
      maxV = Math.max(maxV, (double) sum / k);
      for (; i < nums.length; i++) {
          sum = sum - nums[i - k] + nums[i];
          maxV = Math.max(maxV, (double) sum / k);
      }
      return maxV;
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashSet<Integer> set = new HashSet<>();
        int right = 0;
        
        // 初始化构造窗口
        while (set.size() < k) {
            set.add(nums[right++]);
        }
        while(right < nums.length)
            if (set.contains(nums[right])) {
                return true;
            }
            set.remove(nums[right-k]);
            set.add(nums[right]);
            right++;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
  public List<Integer> findAnagrams(String s, String p) {
        int len = s.length();
        int right = 0;
        int plen = p.length();
        ArrayList<Integer> list = new ArrayList<>();
		// 保证p比s短
        if (plen > len) {
            return list;
        }
      
        int[] mp = new int[26];
        int[] targetmp = new int[26];
        int mpSize = 0;
		// 记录p中各个字符出现的次数
        for (int i = 0; i < plen; i++) {
            targetmp[ p.charAt(i) - 'a'] ++;
        }

        while (right < len) {
            char c = s.charAt(right);
            mp[c-'a']++; mpSize++;
            // while和if效果是一样的，因为mp大小是通过right一次次增大的
            if (mpSize > plen) {
                // 缩小左边界
                char removeChar = s.charAt(right - plen);
                mpSize--;
                mp[removeChar-'a']--;
            }
            if (right(mp, targetmp)) {
                list.add(right - plen + 1);
            }
            right ++;
        }

        return list;
    }

    private boolean right(int[] chars1, int[] chars2) {
        for (int i = 0; i < chars1.length; i++) {
            if (chars1[i] != chars2[i]) {
                return false;
            }
        }
        return true;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
     public int equalSubstring(String s, String t, int maxCost) {
        int len = s.length();
        int left = 0, right = 0;
        int ans = 0;
        // 现在已经花费的cost
        int cost = 0;
        while (right < len) {
            cost += Math.abs(s.charAt(right) - t.charAt(right));
            // 此时cost不满足条件
            while (cost > maxCost) {
                // 通过移动left, 将cost补偿回来
                cost -= Math.abs(s.charAt(left) - t.charAt(left));
                left++;
            }
            // 求最大长度，则更新在第一层while里面
            ans = Math.max(ans, right - left + 1);
            right ++;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
     public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        int[] ans = new int[len - k + 1];
        int right = 0;
        int idx = 0;
        LinkedList<Integer> list = new LinkedList<>();

        while (right < len) {
            int now = nums[right];
            // 保持list递减
            while (!list.isEmpty() && list.peekLast() < now) {
                list.pollLast();
            }
            list.addLast(now);
            right++;
            if (right >= k) {
                ans[idx++] = list.peekFirst();
                // 下一次的时候将不会再在窗口里面， 所以判断是否出局
                if (list.peekFirst() == nums[right - k]) {
                    list.removeFirst();
                }
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 一开始都没看出来怎么需要用到窗口， 后来发现s1的排列必须是s2的子串, 所以字符是相同的, 子串长度也是固定。 所以是道定长窗口题
class Solution {
  public boolean checkInclusion(String s1, String s2) {
        int[] arr1 = new int[26];
        int[] arr2 = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            arr1[s1.charAt(i) - 'a']++;
        }
        int k = s1.length(), right = 0;
        int len = s2.length();
        int cnt = 0;

        while (right < len) {
            arr2[s2.charAt(right) - 'a']++;
            cnt ++;

            while (cnt > k) {
                arr2[ s2.charAt(right - k) - 'a']--;
                cnt--;
            }
            if (contains(arr1, arr2)) {
                return true;
            }
            right++;
        }
        return false;
    }

    boolean contains(int[] arr1, int[] arr2) {
        for (int i = 0; i < arr1.length; i++) {
            // 一旦arr2不符合
            if (arr1[i] > arr2[i]) {
                return false;
            }
        }
        return true;
    }
}

参考文章：

Author: Mrli

Link: https://nymrli.top/2022/04/10/算法与数据结构——滑动窗口/

Copyright: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.

< PreviousPost
总得学点Elasticsearch吧NextPost >
[翻译]设计Pastebin.com(or Bit.ly)系统
CATALOG
  1. 1. 基本概念
  2. 2. 核心思路
  3. 3. 代码模板
    1. 3.1. 变长窗口模板
    2. 3.2. 固定长窗口模板：
  4. 4. easy point:
  5. 5. 一起做几题
  6. 6. 参考文章：