算法总结-滑动窗口

滑动窗口通常应用在从字符串中寻找满足条件的子串一类的题目中，是上文中双指针算法的一种特殊形式。滑动窗口算法的关键是需要一个数组来记录下当前窗口中每个字符的数目，然后再根据具体的条件来移动窗口前后的指针。

LeetCode3

题目链接：

https://leetcode.com/problems/longest-substring-without-repeating-characters/

题目描述：

从一个字符串中找到一个最长的不包含重复字符串的子串，然后返回其长度。

例子

1
2
3

Input: "pwwkew"
Output: 3 
Explanation: 最长子串为 "wke", 其长度为 3.

题目分析：
题目可以使用双重循环对每个子串进行判断，但是效率不高，使用滑动窗口可以在O(N)的时间复杂度下解决问题。窗口的滑动总共分为3步：

窗口右边往前滑动，同时记录好窗口内都有哪些字符。这一步需要提前创建个数组map记录下每个字符已经是否包含在窗口中。
判断窗口那的子串是否满足需求。这一步同样是通过map数组来判断，如果数组中没有这个字符的记录，可以认为当前是一个可能的解。
窗口左边往前滑动到窗口中没有重复字符了为止。在滑动的过程中将遇到的字符从数组中减去。

代码：

int lengthOfLongestSubstring(string s) {
    vector<int> map(128, 0);//记录下窗口中出现过的字符
    int longest = 0;
    int i = 0, j = 0;
    while(j < s.size()) {
        if(!map[s[j]]) {//数组中没有当前的字符串，找到一个可能的解。
            longest = max(longest, (j - i + 1));
        } else {//数组中有记录当前的字符串，出现重复。
            while(i < j && map[s[j]] > 0) {//将窗口左侧往前滑动，直到当前窗口内没有重复字符串为止。
                map[s[i]]--;
                i++;
            }
        }
        
        map[s[j]] ++;
        j++;
        
    }

    return longest;
}

LeetCode76

题目链接：

https://leetcode.com/problems/minimum-window-substring/

题目描述：

给定两个字符串 S 和 T, 在O(N)的时间复杂度前提下从 S 中找到包含 T 中所有字符的最短子串。

例子：

1 2	Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC"

题目分析：

由于题目要求O(N)的时间复杂度，所以这里首先就考虑使用滑动窗口来解决。和之前一样，首先创建一个数组来记录窗口内字符的数目，但是这一次数组要初始化为 T 中的每个字符的数目，如例子中字符’A’, ‘B’和’C’在数组中对应的数字为1，其它的都为0。

在窗口右侧滑动的过程中，在数组中将所遇到的字符数目减一。当数组中所有的数都小于等于0时，就代表找到了一个可能的解。之后需要移动窗口作则，与右侧相反在数组中将所遇到的字符数目加一。由于左侧的前部可能包含一些不在 T 中的字符，所以可能在左侧移动之后数组中所有的数还都小于等于0，这说明找到了一个更优的解。当数组中出现了大于0的数值时，说明现在窗口内的字符串是不满足要求的，需要继续滑动窗口的右侧来寻找。

代码：

string minWindow(string s, string t) {
    vector<int> map(128, 0);
    for(auto c : t) { //初始化数组为t中各个字符的个数
        map[c]++;
    }

    int count = t.size();
    int i = 0, j = 0;
    pair<int, int> result = {0, s.size()};//记录最短字符串的起始位置和长度

    while(j < s.size()) {
        if(map[s[j]] > 0) {// s[j]在t中，找到一个字符串，count减一
            count--;
        }
        map[s[j]]--;//将数组中对应的字符数目减一并往前移动窗口
        j++;
        while(count == 0) {//找到了可能的解
            if(j - i < result.second){
                result = {i, j - i};//找到了更优的解
            }

            if(map[s[i]] == 0){//s[i]是包含在 t 中的字符，窗口左侧往前移动后，需要查找的字符数目加一
                count++;
            }
            map[s[i]]++;//移动窗口左侧并将对应的字符数目加一
            i++;
        }

    }
    
    return s.substr(result.first, result.second);
}

LeetCode239

题目链接：
https://leetcode.com/problems/sliding-window-maximum/

题目描述：

有一个长度为k的滑动窗口，从一个数组的左侧向右滑动。返回滑动窗口中每一步最大的值。

例子：

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[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

题目分析：
这是一道困难级别的题目，想要在O(N)的时间复杂度下解决就需要使用到deque。deque是这样一种队列，即从其头部和尾部就可以进行复杂度为O(1)的插入和删除操作，但是如果频繁地在其中间进行插入和删除操作，其性能就不如普通的链表了。著名的LRU缓存内部一般就是用deque来实现的，最近使用的数据从头部进行插入，当缓存满了的时候就从尾部进行删除。

回到本题中，deque将用来保存当前窗口中较大数据的坐标集合，并且从头部到尾部递减，这样头部坐标对应的数据就是当前窗口中最大的数据。而为了保证deque中对应的数据是递减的，就需要在插入新的数据坐标时进行判断，当前的数据是否比尾部的数据大，如果是则将尾部较小的数据坐标给删除掉，然后将当前数据插入到尾部。那会不会删除掉的数据会是可能的最大值呢？是不可能的。这是因为随着窗口的滑动，新插入的数据必然会比之前的数据“活得”更久，所以在以后的窗口中最大的数据就有可能是这个新插入的这个较大的数据。

deque头部的数据是最大值，那什么时候将头部的数据删掉呢？当然是当窗口滑出头部数据所在的位置，此时新的头部数据就是下个滑动窗口的最大值。

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    if(nums.empty()) return {};
    vector<int> result;
    deque<int> q;
    
    for(int i = 0; i< nums.size(); i++) {
        while(!q.empty() && nums[q.back()] < nums[i]) {
            q.pop_back();//删掉所有尾部较小的值的坐标，这些值不可能是最大值了
        }
        q.push_back(i);//将当前数值坐标插入到尾部，保持队列有序递减
        
        if(q.front() + k == i){
            q.pop_front();//头部的数据的坐标已经滑出窗口了，将其删除
        }
        if(i >= k - 1){//窗口的右侧从 k - 1 开始滑动，k - 1 之前还没有窗口不能取最大值
            result.push_back(nums[q.front()]);
        }
    }
    
    return result;
}

LeetCode424

题目链接：

https://leetcode.com/problems/longest-repeating-character-replacement/

题目描述：

给定一个仅包含大写字母的字符串，最多更改k个字母，计算出更改后连续字母的最大长度。

例子：

Input:
s = "ABAB", k = 2

Output:
4

Explanation:
可以将两个'A'改为'B'，结果为"AAAA"，长度为4.

题目分析：

当滑动窗口右侧滑动的时候，窗口的长度会增加，此时如果窗口的长度等于窗口中数目最多的字母数加上k, 则这个窗口就是一个可能解。只要将所有可能的解都找出来，取其中最长的就是最终的结果。

代码：

int characterReplacement(string s, int k) {
    int result = 0;
    int maxC = 0; //记录窗口中字母最多的字母数
    vector<int> v(26);
    for(int i = 0, j = 0; j < s.size(); j++){
        maxC = max(maxC, ++v[s[j] - 'A']); //窗口右侧往前滑动，更新一下最多的字母数
        while(j - i + 1 - maxC > k){ //窗口太长了，将左侧往前移动
            v[s[i++] - 'A']--;
        }
        
        result = max(result, j - i + 1); //当前窗口是一个可能的解，记录下最长长度
    }
    return result;
    
}

LeetCode567

题目链接：

https://leetcode.com/problems/permutation-in-string/

题目描述：

给定两个只包含小写字母的非空字符串s1和s2，判断是否有一个s1中字母的任意组合是s2的子串。

题目分析：

s2是比较长的的字符串，需要在s2上应用滑动窗口。和之前一样，可以先建一个数组，将s1中每个字符的数目给记录下来，当窗口在s2上滑动时，对右边碰到的字符就将其数目减一，对左边碰到的字符就将其数目加一。同时滑动的过程中还要确保窗口中的字符都包含在s1中，而且每个字符的数目不能多于s1中对应字符的数目。这样当数组中记录的数字都为0而且窗口的长度恰好等于s1时，就说明找到了这样的一个子串。

代码：

bool checkInclusion(string s1, string s2) {
	vector<int> map(26, 0);
	for (auto c : s1) { //记录下s1中每个字符的数目
	    map[c - 'a']++;
	}
	
	for (int l = 0, r = 0; r < s2.size(); r++) {
	    int index = s2[r] - 'a';
	    map[index] --; //窗口右侧滑动，对应字符数目减一
	    if (map[index] < 0) { //字符数目小于0，说明窗口中有不包含在s1中字符或者某个字符数目超过了s1中相同字符的数目，需要缩小窗口
	        while(s2[r] != s2[l]) {
	            map[s2[l] - 'a']++;
	            l++;
	        }
	        map[s2[l] - 'a']++;
	        l++;
	    } else if (r - l + 1 == s1.size()){// 窗口的长度等于s1的长度，找到了一个子串
	        return true;
	    }
	}
	return false;
}

总结

解决滑动窗口的题目一般都是通过一个数组来记录下字符的数目，然后在窗口的滑动过程中对数组中的数目进行加减，最后分析窗口左右两边滑动的条件。在明确了窗口的滑动条件后，就不难找出目标解了。