Leetcode Hot 100 | 滑动窗口

思想

今天起的很早，来到编译原理的教室，空无一人，打开窗户换换气。果然到了大三，谁还会提早这么早到教室自习呢？校圈上、网络上总是有人询问所谓的通宵自习室在哪里，其实若能早起，能自习的地方有很多。

在本节，我们将见到两种类型的滑动窗口题型，同向而行与固定窗口大小。其中前者是双指针的一种，而后者一个指针就够了。滑动窗口的思想是增量更新，每到达一个新的位置后，只需要去掉边界外的值，增加新进来的值，而不需要对每个窗口进行遍历。

题目

3. Longest Substring Without Repeating Characters

这题要求我们找出字符串的最长子串，这个子串不含重复字符，而且是所有子串中最长的。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0;
        int len = 0;
        vector<int> cnt(128, 0);

        for (int right = 0; right < s.size(); right++) {
            cnt[s[right]]++;

            while (cnt[s[right]] > 1) {
                cnt[s[left]]--;
                left++;
            }

            len = max(len, right - left + 1);
        }

        return len;
    }
};

增量更新，是个好词，早起的时候或许能迸发很多灵感。既然是增量更新，那就需要用空间换时间，找个数组或者类似的存储结构维护当前窗口的信息，这里选择了一个长度 128 的向量，因为题目说输入是 ASCII 字符。

思路是什么呢？每次只需要判断边界的情况就行了，因为中间的元素状态是稳定的，不会引入变化。对于右侧的边界，每次访问它，看看它是否在窗口中出现了多次，如果有，则缩小左侧窗口，直到窗口没有重复字符存在。

我当时学习滑动窗口的时候，有一个疑问，不理解，为什么这样做就能讨论所有情况了。嗯，确实，滑动窗口非常有条理，但我总觉得不踏实，好像差了点什么。

那我们不妨慢慢来，用人的思维思考，不要考虑变量的维护。首先，起点是数组的第一个元素，右侧指针想尽量右移，贪心地右移吧！什么时候是个头呢：当出现重复字符的时候。哦不！这时候必须记录一下我们的成果了，因为右侧指针再右移就非法了。

那我问你，这时候怎么办？右侧指针再右移吧！可不管右移多远都没用，因为重复字符已经出现了。这么说，必须右移左侧指针了。可是，这会不会错过什么？如果用暴力的思路，好像应该考虑左侧指针指向每个字符的情形，为什么会这样气定神闲地右移左指针，直到重复字符不出现？

我们思考一下，刚刚已经获得了上一轮的结果。现在假设右指针指向重复字符出现的前一个位置，也就是最后一个合法位置，因为这样可以保证从起点开始，右侧的边界取得最大值。这么一来，讨论起点是第二个字符位置就无意义了——因为它是之前结果的子串，长度必然小于最好的结果。

好，到目前为止，我们搞清楚了如果右侧指针指向最后一个合法位置，左侧指针不必考虑第二个字符的原因。但是，当右侧指针指向重复字符时，滑动窗口算法有没有遗漏这个情形？

讨论了的。现在右侧指针指向重复字符，当左侧指针指向第二个字符时，上方的算法中有一个条件判断：如果指向这个位置，使得这个子串是合法的，那才有讨论价值。此时，这个位置可以作为新的起点，再考虑右侧指针向后的情形。

说了这么多很啰嗦。我想，可以这样来理解。

1 *2* 3 4 5 6 *7* 8 9

假如 2 - 7 是当前最优的子串，固定右指针在 7 不变。对于左侧指针，没必要考虑 3 - 6（除非右侧指针指向 8 及之后），因为它们比现在的解差；1 已经考虑过了，因为如果它在右指针指向 7 的时候还能取得，那左指针不会指向 2，应该还在 1 的位置。形成当前格局只能说明左指针指向 1 会包含重复字符。

76. Minimum Window Substring

这题要求我们找出最小长度的子串，这个子串包含了目标字符串中的所有字符，顺序无所谓（种类和每个种类的个数都要满足）。

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> need(128, 0);
        vector<int> window(128, 0);

        for (char c : t) {
            need[c - '0']++;
        }

        int required = 0;
        int valid = 0;

        for (int i : need) {
            if (i > 0) required++;
        }

        int left = 0;

        // 子串结果
        int start = 0;
        int len = INT_MAX;

        for (int right = 0; right < s.size(); right++) {
            int c = s[right] - '0';
            window[c]++;

            if (need[c] > 0 &&  need[c] == window[c]) {
                valid++;
            }

            while (valid == required) {
                if (right - left + 1 < len) {
                    start = left;
                    len = right - left + 1;
                }

                int c = s[left] - '0';
                left++;

                if (need[c] && need[c] == window[c]) {
                    valid--;
                }

                window[c]--;
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

这题是道 Hard，和前一道题的思路类似，还是同向窗口。

为了实现增量更新，需要先做初始化。初始化满足两个需求：记录每个字符的数量以及字符的种类数。思考思考，前者是肯定要记录的，而后者我觉得是用空间换时间，这样检查条件是否满足时不必遍历整个数组。

初始化完毕，窗口的状态也用两个变量来满足，分别记录当前窗口中每种字符的数量，以及满足数量要求的字符的种类数。

现在窗口可以开始滑动了。从起点开始，先找到第一个满足要求的串。每次滑动右侧时，需要增量更新，增加当前字符的数量，以及看看是不是有新种类的字符满足了要求。

如果满足了要求，则窗口可以收缩了。每次收缩的时候，记录最优解，同时要增量更新，把界限外的字符删掉。

左侧指针移动到什么位置才停止？移动到窗口非法。换句话说，要找到最小的满足要求的窗口，有点类似于极大无关组的概念。否则，再记录的结果都包含了最小值，肯定不是最优的。

239. Sliding Window Maximum

这道题要求我们滑动一个长度为 k 的窗口，返回一个向量，记录每个窗口的最大值。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> result;

        for (int i = 0; i < nums.size(); i++) {
            // 移除窗口外的
            if (!dq.empty() && dq.front() <= i - k) {
                dq.pop_front();    
            }
            
            // 移除比当前值小的
            while (!dq.empty() && nums[dq.back()] < nums[i]) {
                dq.pop_back();
            }

            // 添加当前值
            dq.push_back(i);

            // 如果窗口构建完毕，记录结果
            if (i >= k - 1) {
                result.push_back(nums[dq.front()]);
            }
        }

        return result;
    }
};

这题是个固定大小的滑动窗口，不再需要左右两个指针了，但是还需要维护状态。这里，状态用一个单调队列来维护，具体的实现方法是双端队列，一边出，一边进。这个队列中，队首 >= 队尾，队首记录了当前窗口范围内的最大值。

开始滑动吧！每次滑动的时候，要先移除窗口外的，这是增量更新的体现。

此外，要在队列中移除比当前值小的，因为比当前值小的不可能成为窗口中的最大值。

如果定量分析，这个队列的长度 <= k，那么队列中的每个元素都是当前窗口中的元素（且未来可能成为窗口的最大值）。那么关于它的维护就清晰了：落后于时代的要弹出，后生小子会顶掉前面比它小的。

注意的一点是，后生小子替换时，从队尾开始。

之后，后生进入队列，不管怎样它都要进入队列，因为它是最年轻的，至于说它能撑多久，要看后浪有多激烈——但目前为止，它能活最久。所以说，能待在窗口里的元素，总得有一技之长，要么能力强，要么年轻，总得占一个，中不溜的就无地自容了。

最后，当窗口到达合法范围后，再构建结果。

438. Find All Anagrams in a String

这题要求我们找出字符串的所有子串，它们是目标串的变位词。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> need(26, 0);
        vector<int> window(26, 0);

        vector<int> result;

        for (char c : p) {
            need[c - 'a']++;
        }

        int k = p.size();

        for (int i = 0; i < s.size(); i++) {
            if (i - k >= 0) {
                window[s[i - k] - 'a']--;
            }

            int c = s[i] - 'a';
            window[c]++;

            if (i >= k - 1 && need == window) {
                result.push_back(i - k + 1);
            }
        }

        return result;
    }
};

还是滑动固定窗口。这里，状态采用类似的数组方式来维护。

滑动窗口时，还是移除窗口外的字符，加入新的字符。并判断是否满足要求。

这里比较取巧的地方是，可以直接用向量的比较。此外， i >= k - 1 其实可以省略。