滑动窗口算法深度解析_动态滑窗时间复杂度

滑动窗口是解决数组和字符串问题的利器，其根据当前窗口内子序列的情况，不断调整子序列的起始位置，从而将时间复杂度从 O(n^2)转化为O(n)可以说是十分优雅。

其本质就是维护一个动态调整的区间（窗口），通过移动窗口边界（滑动），实现对窗口内数据的处理。

其常被用于解决一定条件下的连续区间的性质、长度、和等问题。

其核心思想如下：

1. 构造窗口：由left和right两个指针组成。窗口就是两个指针之间的子序列，两个指针都始于左边界，并一前一后地向右边界前进。
2. 窗口扩张：未达期望（没有得到最终结果）前，**right不断向右移动**，直到满足期望或到达右边界。
3. 窗口收缩：一旦窗口扩张满足甚至超出窗口的形成条件，**left向右移动**，缩小窗口去除多余的部分，直到窗口恰好不满足条件。这一过程中，结合窗口的尺寸更新全局最优解。之后right再次前进，直至抵达右边界。
4. 故，实现过程中只需要注意窗口以及左右指针分别是什么即可。

举例如下：

209. 长度最小的子数组 - 力扣（Leetcode）

在该题中实现滑动窗口主要确定三点：

1. 窗口内是什么？（满足条件的最小的连续子数组）
2. 左指针什么条件移动？（若窗口大于target了（不满足窗口形成条件），窗口要向前移动，即缩小）
3. 右指针什么条件下移动？（右指针代表窗口的结束位置，每轮循环中都向右移动）

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int len = INT_MAX;
        int left = 0,right = 0;
        int sum = 0;
        while(right < nums.size()){
            sum += nums[right];
						// left > right时，sum 就会减为负数而target是正数所以不会发生左边界超过右边界的情况
            while( sum >= target){  
                len = min(len,right - left + 1 );
                sum -= nums[left];
                left++;
            }
            right++;
        }
        return len == INT_MAX ? 0: len;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

注：在写代码时一定要注意left变化和sum变化的时机。例如在内层while循环中，首先left++，然后再sum -= num[left];sum就会减去窗口后面的值，就错了。

模板

void slidingWindow(string s, string t) {
		// 记录窗口内和待对比信息，用来对比
    unordered_map<char, int> need, window;
		// 初始化带对比信息
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    // 比对window和need是否符合条件的计数器，一个字符达到条件valid加1
		int valid = 0; 
		
		//部分固定窗口类题目，可以先在外面初始化第一个窗口，之后从第一个窗口之后逐个滑窗口
		for(int i = 0;i<k;i++) xxx 
    // 窗口扩张
		while (right < s.size()) {
        char c = s[right];
        right++;
        // 更新窗口数据
				...
				cout<<left<<" "<<right<<endl; // debug,查看必要数据
        
        // 收缩窗口，若是固定长度窗口while并无必要（因为每次都会固定删掉一个）
        while (window needs shrink) {
            char d = s[left];
            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

练习

3. 无重复字符的最长子串 - 力扣（LeetCode）

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> st;
        int ans = 0;
        int left = 0, right = 0;
        while(right < s.size()){
            if(st.find(s[right]) != st.end()){ // 找到重复字符
                st.erase(s[left]);
                left++;
            }else{  // 没有找到重复字符，将当前字符添加到st中
                st.insert(s[right]);
                ans = 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

76. 最小覆盖子串 - 力扣（LeetCode）

写法与常规问题一致，但是本题判断窗口是否需要缩小有点麻烦。窗口满足条件时，当前窗口内子串可以覆盖t中子串。这个该如何判断？每次都遍历数数时间复杂度肯定很高，所以只能用哈希表记录下来，用空间换时间。

• 使用两个哈希表 window 和 need 分别记录窗口内的字符以及 t 中各字符所需出现的次数。
• 在扩展窗口右边界时，对于新增加的字符c，只关注其是否是t中出现过的字符。如果t中出现过，则window[c]++;然后判断windows[c] == need[c]（c在窗口内出现的次数达到了t中出现的次数），则valid++;（valid用于跟踪窗口内已经覆盖了t中多少个不同的字符）
• 当valid的值等于need.size()时，表示t中所有字符都已经被当前窗口覆盖。这时，就找到了一个“最小覆盖子串”嫌疑人，需要更新结果并尝试缩小窗口以探索更小的覆盖子串。

注：

• 要注意need和t的区别。t是字符串，need是记录t中字符个数的哈希表，有时候用的是t有时候用的是need。
• 在处理哈希表时，要明确操作顺序：
  • 在添加字符时，应该先操作再判断。因为比较的是添加字符后是否符合条件。
  • 在移除字符时，应该先判断再操作。因为只有符合条件移除条件才需要valid--

class Solution {
public:
    string minWindow(string s, string t) {
        int left = 0,right = 0; // 左右指针，标记窗口范围
        int start = 0; // 标记结果字串的开始位置（因为要找最小的字串，所以最终结果的起始位置不一定是left）
        int valid = 0;  // 表示窗口中可以覆盖的字符数
        int minLen = INT_MAX;
        unordered_map<char,int> windows,need; // 记录窗口中和需要比较的字符的个数
        for(char c : t) need[c]++;
        while(right < s.size()){
            char c = s[right];
            right++;
            if(need.count(c)){
                windows[c]++;
                if(windows[c] == need[c]) valid++;
            }
            // 缩小窗口
            while(valid == need.size()){
                // 更新结果
                if(right - left < minLen){ //由于上面已经right++了，这里子串长度就是right - left
                    minLen = right - left;
                    start = left;
                }
                char d = s[left];
                left++;
                if(need.count(d)){
                    if(windows[d] == need[d]) valid--;
                    windows[d]--;
                }
            }
        }
        return minLen == INT_MAX ? "": s.substr(start,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
29
30
31
32
33
34

239. 滑动窗口最大值 - 力扣（LeetCode）

本题中窗口是固定大小，且需要求的是最大值。所以需要一个数据结果来保证可以获取最大值，可以用优先队列，也可以利用单调栈。这里采用双端队列。

1. 在窗口扩展时，维护一个单调栈，保证可以随时取到当前窗口内的最大值。
2. 窗口缩小不是简单left++，而是通过双端队列中存储的索引判断当前队列头部的最大值是否还在窗口内，不在了就移除出去。（因为最后求的是最大值而不是窗口大小，所以left不需要记录）

注：

• 时刻牢记，双端队列中存储的是索引。（如果存储的是最大值的话在窗口缩小的时候就不知道当前最大值是啥了）

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int left = 0, right = 0;
        deque<int> deq; // 维护最大值
        vector<int> ans;
        while(right < nums.size()){ 
            // 窗口扩展时，维护一个单调栈保证能取到最大值
            while(!deq.empty() && nums[deq.back()] < nums[right]) deq.pop_back();
            deq.push_back(right);
            // 缩小窗口
            while(!deq.empty() && deq.front() < right - k + 1) 
                deq.pop_front();
            // 更新结果
            if(right >= k - 1 )
                ans.push_back(nums[deq.front()]);
            right++;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

424. 替换后的最长重复字符 - 力扣（LeetCode）

在解决这个问题时，我们的核心任务是确定何时缩小滑动窗口的大小。我们需要找到一个子串，该子串在最多替换 k 个字符后，所有字符都能变得相同。

为了实现这一点，我们维护一个哈希表来记录窗口内各个字符出现的频次，同时跟踪出现次数最多的那个字符的频次（rep）。基于这个信息，可以得出窗口缩小的关键条件：当窗口的大小减去 rep 的值大于 k 时，即便我们替换 k 个字符，也无法让窗口内的所有字符完全相同。这是因为窗口内还有超过 k 个的其他字符存在。

在这个逻辑下，我们不断扩大窗口直至满足上述条件。一旦条件满足，我们就开始缩小窗口，直到窗口内可以通过替换 k 个字符来统一所有字符。通过这种方式，我们能够找到并返回满足条件的最长子串的长度。这个过程中，窗口的实时大小提供了我们正在考虑的子串的长度，而哈希表中记录的频次信息则决定了何时需要调整窗口的边界。

class Solution {
public:
    int characterReplacement(string s, int k) {
        int left = 0, right = 0;
        int rep = 0; //窗口内重复次数最多的字符重复了多少次
        vector<int> window(26,0); //记录窗口内各个字符出现的次数
        while(right < s.size()){
            char c = s[right];
            window[c - 'A']++;
            rep = max(rep,window[c - 'A']);
            right++;
            // 窗口大小减去本身重复的最多的字符个数 超过了k表明即使换k次也无法将窗口内字符全换成一样的了，需要缩小窗口
            while(right - left - rep > k ){
                char d = s[left++];
                window[d - 'A']--;
            }  
        }
        return right - left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

窗口、窗口的左右边界是什么都很直观。关键还是如何判断窗口收缩和如何判断是否找到了结果。

• 窗口收缩：由于异位词指由相同字母重排列形成的字符串，所以窗口收缩的条件就是窗口大小和p的长度相等了。（达到临界条件，继续不收缩的话就再也得不到结果了）
• 判断结果（异位词）：直观的方法就是窗口内的子串和p比一比字符个数，但太浪费时间。还是和前面一样，用空间换时间。用一个window存储s中字符个数，need存储p中字符的个数。当有一个字符相等valid就加1，valid等于need.size()表明找到了一个结果。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int left = 0, right = 0;
        int valid = 0;
        unordered_map<char,int> window;
        unordered_map<char,int> need;
        for(char c : p) need[c]++;
        vector<int> ans;
        while(right < s.size()){
            char c = s[right];
            right++;
            if(need.count(c)){
                window[c]++;
                if(window[c] == need[c]) valid++;
            }
            // 窗口大小和p一样时，窗口收缩
            while(right - left == p.size()){
                if(valid == need.size()) ans.push_back(left); //是异位词，将索引放入结果
                char d = s[left];
                left++;
                if(need.count(d)){
                    if(window[d] == need[d]) valid--;
                    window[d]--;
                }
            }
        }
        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

480. 滑动窗口中位数 - 力扣（LeetCode）

这个一看看过来和239. 滑动窗口最大值 - 力扣（LeetCode）太像了，一个是求最大值，一个是求中位数。这里的关键就是：窗口变化过程中如何求得中位数。

• 直接暴力数一数大概率会超时。毕竟求中位数的过程中需要实时排序。
• 可以考虑通过维持一个有序的数据结构来解决，比如：平衡二叉树（C++中可以用multiset）,实现对数时间复杂度的插入和删除操作。
  • 使用multiset时，初始状态不应该是空集合。因为在通过mid = next(window.begin())定位中位数的迭代器时，若集合为空，则window.begin()实际上等同于window.end()，这种情况下进行next操作相当于越过了容器末端，这是未定义的行为可能导致程序崩溃。
  • mid 迭代器代表窗口内当前的中位数。由于窗口的大小固定为 k，因此窗口的有效范围是从 window.begin() 到 window.begin() + k。在窗口内进行元素的插入和删除操作时，必须谨慎处理 mid 迭代器的移动：
    • 在插入元素时，若新元素小于*mid，该元素就会插入到mid前面。此时，中位数在窗口内的位置就会向右偏移一格。如果新元素大于等于*mid，则不会影响mid的位置，因为新元素位于mid之后的位置，mid本身还指向窗口的中位数。
    • 在移除元素时，如果插入的元素小于等于*mid，表明移除了中位数左侧的元素。因此，mid在窗口中的位置会往左偏移一格，此时需要mid++让mid回到窗口的中间位置。
• 也可以维持两个优先队列（一个大顶堆，一个小顶堆）。大顶堆保存较小的一半元素，小顶堆保存较大的一半元素。中位数可以通过比较两个堆的顶部元素得到。（经典的大小堆思想，在295. 数据流的中位数 - 力扣（LeetCode）中也用过）
• 本题我的写法有些奇怪，但主要还是为了统一滑动窗口类题目代码风格。

// 这里采用multiset
class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        int left = 0, right = k;
        multiset<int> window(nums.begin(),nums.begin() + k);
        auto mid = next(window.begin(),k / 2);
        vector<double> ans;
        while(true){
            ans.push_back(((double)(*mid) + *prev(mid,1 - k % 2)) / 2);
            if(right == nums.size()) break;
            window.insert(nums[right]);
            if(nums[right] < *mid) mid--;
            while(right - left == k){
                if(nums[left] <= *mid) mid++;
                window.erase(window.lower_bound(nums[left]));
                left++;
            }
            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

567. 字符串的排列 - 力扣（LeetCode）

• 本题我的写法有些奇怪，但主要还是为了统一滑动窗口类题目代码风格。

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if(s1.size() > s2.size()) return false;
        int k = s1.size();
        int left = 0,right = k - 1 ;
        vector<int> cnt1(26,0);
        vector<int> cnt2(26,0);
				// 用两个vector存储窗口和need的
        for(int i = 0;i<k - 1;i++){
            cnt1[s1[i] - 'a']++;
            cnt2[s2[i] - 'a']++;
        }
				//s1没有记录全，之后的循环主要是遍历s2，所以进去前先把s1搞齐
        cnt1[s1[k -1] - 'a']++;  
        while(right < s2.size()){
            cnt2[s2[right] - 'a']++;
            if(cnt1 == cnt2) return true;
						//这个判断其实是没必要的,所有窗口大小固定的题目，每次都要收缩一次。这里只是为了风格
            while(right - left + 1 == k){ 
                cnt2[s2[left] - 'a']--;
                left++;
            }
            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

992. K 个不同整数的子数组 - 力扣（LeetCode）

一上头靠着直觉写了个，然后错了。错误代码如下：该代码忽略了一种情况:对于一个固定的左边界，满足「恰好存在 K 个不同整数的子区间」的右边界 不唯一，且形成区间。例如，1，2，1，2，3中，设k = 2，则1,2和1,2,1和1,2,1,2都符合条件。

对于以上这种情况，本代码在遇到满足条件的窗口后就直接缩小窗口大小的思路明显漏数了。

所以整个寻找恰好k个不同整数的思路是错的。（还是小觑了困难题目呀）

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        int left = 0, right = 0;
        int ans = 0;
        int valid = 0;
        unordered_map<int,int> mp;
        while(right < nums.size()){
            mp[nums[right]]++;
            while(k == mp.size()){
                ans++;
                mp[nums[left]]--;
                if(mp[nums[left]] == 0) mp.erase(nums[left]);
                left++;
            }
            right++;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

如果不是恰好k个不同整数，而是最多k个不同整数，右边界就可以确定下来了。所以可以将问题转换为：最多包含k个不同整数的子数组 - 最多包含k - 1个不同整数的子数组 = 恰好包含k个整数的子数组。而最多包含可以很容易得用传统滑动窗口解决。

class Solution {
public:
    int mostK(vector<int>& nums,int k){
        int left = 0, right = 0;
        int ans = 0;
        unordered_map<int,int> mp;
        while(right < nums.size()){
            mp[nums[right]]++;
            while(mp.size() > k){ // 不同整数数量超过k了，收缩窗口
                mp[nums[left]]--;
								// 整数计数变为0时，要将其从mp中彻底删除，否则会一直计数
                if(mp[nums[left]] == 0) mp.erase(nums[left]);
                left++;
            }
						// 最多包含k个不同整数，所以[1,2,1]中有[1],[1,2],[1,2,1]三个
            ans += (right - left + 1);
            right++;
        }
        return ans;
    }
    int subarraysWithKDistinct(vector<int>& nums, int k) {
				// 恰好k个不同整数 = 最多k个整数 - 最多k - 1个整数
        return mostK(nums,k) - mostK(nums,k -1);
    }
};
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

904. 水果成篮 - 力扣（LeetCode）

写完上一题再写这个就轻松很多，这个就是最多k个不同整数的最长子数组。

• 不过这里的k固定是2（两个篮子）。
• 这里求的不是这样的子数组的总数，而是最长的包含k个不同整数的子数组长度。

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int left = 0 ,right = 0;
        int k = 2; //标记最多k个不同整数
        unordered_map<int,int> mp;
        int ans = 0;
        while(right < fruits.size()){
            mp[fruits[right]]++;
            while(mp.size() > k){
                mp[fruits[left]]--;
                if(mp[fruits[left]] == 0) mp.erase(fruits[left]);
                left++;
            }
            ans = 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

978. 最长湍流子数组 - 力扣（LeetCode）

湍流子数组就是数组中元素大小看起来是一上一下的。对于湍流子数组中的任何连续的三个元素arr[i-1]、arr[i]、arr[i+1]，要么满足arr[i-1] < arr[i] > arr[i+1]，要么满足arr[i-1] > arr[i] < arr[i+1]。

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int left = 0,right = 0;
        int ans = 1;
        if(arr.size() == 1) return 1;
        while(right < arr.size() - 1){
            if(left == right){
                if(arr[right] == arr[right + 1]) left++;
                right++;
            }
            else{
                // 加入当前arr[right]后还是湍流子数组，扩展窗口
                if( (arr[right] > arr[right - 1] && arr[right] > arr[right + 1]) ||
                   (arr[right] < arr[right - 1] && arr[right] < arr[right + 1])) 
                   right++;
                // 加入后就不是了（收缩窗口）
                else
                    left = right;
            }
            ans = max(ans,right - left + 1);
        }
				// 考虑最后一个元素，因为其之后没有元素了，其只要和前一个元素不同就能加进去
				// 经过循环后，right一定指向最后一个元素
        if(arr[right] != arr[right -1]) ans = max(ans,right - left + 1);
        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

1052. 爱生气的书店老板 - 力扣（LeetCode）

表面看起来是有两个数组，但对于两个固定的长度一致的数组来说，完全可以当一个来处理。grumpy可以看作customers的一个标记位，标记该处是否需要累加。

核心思路就是：最大满意人数 = 不使用技巧的满意人数 + 使用技巧后挽回的最大人数

使用技巧后挽回的最大人数就可以通过滑动窗口来计算，先初始化第一个窗口，然后每次滑动一格，滑动过程中新增一个元素，去除开头元素，最后更新结果。

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int left = 0,right = minutes;
        int total = 0;  //不发脾气人数
        int maxExtra = 0;  // 最大可挽回人数
        int extra = 0;  // 窗口内可挽回人数
        // 老板不控制自己会有多少人满意
        for(int i = 0;i<customers.size();i++) total += (grumpy[i] ? 0 : customers[i]);
        // 初始化第一个窗口
        for(int i = 0;i<minutes;i++) extra += (grumpy[i] ? customers[i] : 0);
        maxExtra = extra; // 默认第一个窗口为最大值，之后逐步更新
        while(right < customers.size()){
            // 扩展窗口
            if(grumpy[right] == 1) extra += customers[right];
            // 收缩窗口，但对于固定大小窗口来说while并无意义
            while(right - left == minutes){
                if(grumpy[left] == 1) extra -= customers[left];
                left++; 
            }
            // 更新最大值
            maxExtra = max(maxExtra,extra);
            right++;
        }
        // 结果为本来满意人数 + 可挽回人数
        return total + maxExtra;
    }
};
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

1208. 尽可能使字符串相等 - 力扣（LeetCode）

一开始 搞错了以为必须从头开始比，每一个都相等。后来才反应过来，是尽可能相等要尽可能长的连续子字符串相等，就是很普通的一道滑动窗口了。

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int left = 0 ,right = 0;
        int ans = 0;
        while(right < s.size()){
            int temp = abs(s[right] - t[right]);
            maxCost -= temp;
            while(maxCost < 0){
                temp = abs(s[left] - t[left]);
                maxCost += temp;
                left++;
            }
            ans = 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