Just for Life.

明月更几时

0%

算法系列：滑动窗口

发表于
本文字数： 5.3k 阅读时长 ≈ 5 分钟

听到滑动窗口这个词，让我想起了计算机网络中的 TCP 传输和拥塞控制，可惜时隔多年还给老师了，那老师讲课还很不错。我的大部分本科老师都有着很多年的工作经验，并不像部分硕博留校那种只擅长验证玩具理论和咬文嚼字，而从未到实际环境中实习过一次。所以他们讲课十分形象具体，结合理论和实际环境告诉你这是个什么东西。

说远了，回到正题。滑动窗口一般用于求接子串中满足某种情况的最值，可以简单的划分为三类：

  1. 给一个字符串，求满足条件的最长子串
  2. 给两个字符串，求其中一个字符串是否能覆盖另一个字符串
  3. 给定一个数组和窗口大小，窗口没滑动一次，求一次最值

满足条件的最长子串

这个是最简单的一个，也是后面其他滑动窗口的模板。既然是滑动窗口，就必然有一个窗口和滑动的步骤。为了实现窗口，我们定义两个指针，左指针和右指针。随着右指针的移动，窗口逐渐变大，也就是窗口扩张。如果破坏了和满足了题目要求，那么左指针移动，称为窗口收缩，根据题目条件判断窗口收缩的程度，然后当前窗口就是一个满足题意的结果。

随着左右指针的先后移动，会以此查找子串中所有满足情况的子串，我们保留其中的最值即可。说了这么多，来看一个例题，不然太抽象了。

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

我们来分析一下，条件就是不含重复子串，结果就是保留最短的子串长度。既然如此，大概思想就是：

  1. 右指针移动扩张窗口
  2. 当窗口内有重复元素时，收缩窗口，直到没有重复元素
  3. 记录窗口的大小，也就是没有重复字符的子串长度
  4. 重复这个流程，直到求出最长的子串

我们写出程序：

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 lengthOfLongestSubstring(string s) {
        int l = 0, r = 0, n = s.size();
        unordered_map<char, int> m1;
        int ans = 0;
        while (r < n) {
            // 右侧指针滑动
            char c = s[r];
            r++;
            m1[c] ++;
            // 不满足重复条件，因此要收缩，直到满足条件
            while (m1[c] >= 2) {
                char d = s[l];
                l++;
                if (m1[d] >= 2)
                    m1[d] --;
                else if (m1[d] == 1)
                    m1.erase(d);
            }
            // 窗口收缩后，此时满足不重复条件
            // 记录结果
            ans = max(ans, r - l);
        }
        return l == 0 ? n : ans;
    }
};

子串包含问题

567. 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false。换句话说，s1 的排列之一是 s2 的 子串。如 adc 是 kajihscda 的子串。

同样，窗口滑动的时候，把条件判断更改为是否能覆盖 s1 即可：

  1. 右指针移动扩张窗口
  2. 如果能覆盖 s1，收缩窗口，直到不能覆盖 s1
  3. 记录窗口的大小，也就是 s2 中的窗口大小
  4. 判断这个窗口是否为 s1 的排列组合

甚至可以看到，这个和最开始的「无重复字符的最长子串」如出一辙，我们写出程序：

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
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n = s2.size();
        int l = 0, r = 0;
        int valid = 0, res = 0;
        unordered_map<char, int> m1;
        unordered_map<char, int> m2;
        for (auto i : s1)
            m1[i]++;
        while (r < n) {
            char c = s2[r];
            m2[c] ++;
            // 判断是否覆盖子串
            if (m1.count(c) && m1[c] == m2[c]) {
                valid++;
            }
            // 覆盖了，满足题中条件，开始收缩
            while (valid == m1.size()) {
                res = r - l + 1;
                char d = s2[l];
                l++;
                if (m1.count(d) && m1[d] == m2[d]) {
                    valid--;
                }
                m2[d] --;
            }
            r++;
            // 收缩结束，判断这个窗口是否满足结果
            if (res == s1.size())
                return true;
        }
        return false;
    }
};

438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

1
2
3
4
5
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

和上一题一模一样，写出程序保存所有结果即可：

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
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        int n = s.size(), valid = 0, ans = 0;
        unordered_map<char, int> m1;
        unordered_map<char, int> m2;
        for (auto i : p)
            m1[i]++;
        int l = 0, r = 0;
        while (r < n) {
            char c = s[r];
            m2[c]++;
            if (m1.count(c) && m1[c] == m2[c]) {
                valid++;
            }
            while (valid == m1.size()) {
                char d = s[l];
                ans = r - l + 1;
                if (m1.count(d) && m1[d] == m2[d])
                    valid--;
                m2[d]--;
                l++;
            }
            if (ans == p.size()) {
                if (res.empty())
                    res.push_back(l - 1);
                else if (res.back() != l - 1)
                    res.push_back(l - 1);
            }
            r++;
        }
        return res;
    }
};

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。示例：

1
2
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

仿佛不知道说啥，就把上一题的异位词，改成每次保留最短的子串就好了。如出一辙：

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
class Solution {
public:
    string minWindow(string s, string t) {
        if (s.size() < t.size())
            return "";
        int l = 0, r = 0;
        int n = s.size();
        int valid = 0;
        int min_l = 0, min_r = 0, res = INT_MAX;
        unordered_map<char, int> m1;
        unordered_map<char, int> m2;
        for (auto i : t)
            m1[i]++;
        while (r < n) {
            char c = s[r];
            m2[c]++;
            if (m1.count(c) && m1[c] == m2[c]) {
                valid++;
            }
            while (valid == m1.size()) {
                char d = s[l];
                // 每次都保留最短的
                if (r - l + 1 < res) {
                    res = r - l + 1;
                    min_l = l;
                    min_r = r;
                }
                if (m1.count(d) && m1[d] == m2[d]) {
                    valid--;
                }
                m2[d]--;
                l++;
            }
            r++;
        }
        return l == 0 ? "" : s.substr(min_l, min_r - min_l + 1);
    }
};

窗口滑动时求最值

239. 滑动窗口最大值

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

1
2
3
4
5
6
7
8
9
10
11
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

说实话，这是我见过最好的一个数据结构设计类题目。如果每次滑动都遍历求解最大值，是最简单的方法，也是超时的做法，此时就要发挥算法的魅力了：

  1. 我实现一个数据结构，这个数据结构能很快的返回最大值，不需要用户操作什么。虽然很容易想到使用优先级队列，但是优先级队列是不行的，因为优先级队列会破坏元素进入的先后关系，我们不能破坏这一点
  2. 那我们自己定义一个队列，让队首元素是最大值即可，而且队列中的元素降序排列。既然有了队列，那么每次滑动求最大值就容易了，返回队首即可
  3. 且在滑动过程中，如果被滑出去的元素恰好是最大值，那就删除队列中的最大值。由于队列中的元素降序排列，因此下一个队首元素也一定是下一个窗口的最大值
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
class myque{
    int size;
    int max_num;
public:
    myque() {};
    myque(int s) : size{s} {};
    deque<int> q;
    // 自定义队列，保证队列降序
    void push(int num) {
        while (q.size() && num > q.back()) {
            q.pop_back();
        }
        q.push_back(num);
    }
    // 如果滑出去的是最大值，那么就滑走
    void pop(int num) {
        if (num == q.front())
            q.pop_front();
    }
    // 队首即最大值
    int getMax() {
        return q.front();
    }
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        myque q(k);
        vector<int> res;
        // 先填充满窗口
        for (int i = 0; i < k - 1; i++) {
            q.push(nums[i]);
        }
        // 开始滑动
        for (int i = k - 1; i < nums.size(); i++) {
            q.push(nums[i]);
            res.push_back(q.getMax());
            q.pop(nums[i - k + 1]);
        }
        return res;
    }
};

乱入

开头提到讲课的老师，我还是很怀念我大学工程能力很强的老师。

  • 能力低下的老师讲课：我许多年前多么多么厉害，要参加比赛和科研，别人多么不行，你们多么差劲，两个小时的课说一个半小时没用的，这种老师基本硕博留校，上学期间写玩具代码或让别人写，但一定擅长咬文嚼字发文章，也不懂课程内容，只是被分配到了这里。就像我这个博客一样，内容不怎么样，但废话很多。
  • 一般老师讲课：念 PPT，讲一些例题。
  • 比较好的老师讲课：不念 PPT，把课本内容翻译成人话讲出来。
  • 不错的老师讲课，讲完理念，告诉你实际生产环境该如何处理。
本文相关
感谢上学期间打赏我的朋友们。赛博乞讨：我，秦始皇，打钱。

欢迎订阅我的文章