知识铺垫
对于滑动窗口，在分类上，有固定的窗口，也有非固定的窗口，一般是基于数组进行求解。
对于一个数组中两个相邻窗口，会有一大部分重叠的部分，这部分重叠的内容是不需要重复计算的，所以我们可以通过相邻的窗口进行数据的延续使用。
上面两个是长度为4，彼此相邻的窗口，也可以看到，其实大部分数据是相同的，
只是上一个窗口比下一个窗口左端多出一个数据，下一个比上一个右端多出一个数据了。
橙色的点是状态切换之后减少的数据，黄色的点是增加的数据，所以在下一次状态变换时，不用动不变的值，直接修改这两个变化的值就好。
其实我感觉滑动窗口和双指针关系蛮大的…
第一题 1984. 学生分数的最小差值
题目描述
解题报告
通过样例2，小伙伴们应该也能感觉到，排序以后更好处理，那咱就先排序，模拟滑动的过程吧。
① 先确定一个题目要求范围内的窗口： int ans = nums[k-1] - nums[0];
② 更新窗口的首尾元素，模拟窗口滑动的过程
参考代码(C++版本)
class Solution { public: int minimumDifference(vector<int>& nums, int k) { int n = nums.size(); if(n == 1) return 0; sort(nums.begin(),nums.end()); int ans = nums[k-1] - nums[0]; for(int i = k; i < n;i++) //通过循环遍历，模拟滑动的过程 ans = min(nums[i] - nums[i-k+1],ans); return ans; } };
第二题 1876. 长度为三且各字符不同的子字符串
题目描述
解题报告
这种数据范围呢，咋折腾都可以了。解法一就是常规的模拟，比较。
解法二回到咱们今天练习的滑动窗口上，窗口的长度就是题目要求中的3。
参考代码(C++版本)
解法一——想法不要太多，反手直接暴力
class Solution { public: int countGoodSubstrings(string s) { int ans = 0; int n = s.size(); for (int i = 0; i < n - 2; ++i) { if (s[i] != s[i+1] && s[i] != s[i+2] && s[i+1] != s[i+2]) ans ++; } return ans; } };
解法二——可爱滑动窗口
class Solution { public: int countGoodSubstrings(string s) { int l = 0,r = 2; int n = s.size(); int i,j,cnt = 0; bool flag; //开始模拟滑动的过程 while(r < n) { flag = true;//标记当前处理的窗口是否满足要求 for(i = l;i < l + 2;i++) for(j = i+1;j <= l + 2;j++) if(s[i] == s[j]) { flag = false; break; } if(flag) cnt++; l ++,r++;//这种固定窗口长度的了，就得一起滑动了 } return cnt; } };
第三题 1052. 爱生气的书店老板
题目描述
解题报告
先统计一个基础的值吧，在老板不使用这个特殊技巧的时候，把这些满意的客户的数量统计出来。
把使用这个秘密技巧的时候minutes作为滑动窗口的长度，去原数组中遍历，找到因为使用技巧之后，能够获得的最大的满意用户的数量。
注意对第一个窗口的初始化处理。
参考代码(C++版本)
class Solution { public: int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) { int m = customers.size(); int ans = 0;//统计满意的客户的人数 //统计常规情况下，老板不生气的时候，满意的客户的人数 for(int i = 0; i < m;i++) if(!grumpy[i]) ans += customers[i]; //现在统计老板使用这个技巧了，原本不满意的，在这个时间范围内满意了 int tmp = 0; //第一个窗口的情况 for(int i =0; i < minutes;i++) if(grumpy[i] == 1) tmp += customers[i]; //使用技巧之后新增加的用户的数量 int addNum = tmp; //滑动窗口具体滑动的过程了 //在技巧时间内，去挽救那些原本因为生气而不满意的客户 for(int i = minutes; i < m;i++) { if(grumpy[i] == 1) tmp += customers[i]; if(grumpy[i-minutes] == 1) tmp -= customers[i-minutes]; //统计滑动期间的最大值 addNum = max(addNum,tmp); } return ans + addNum; } };
第四题 1839. 所有元音按顺序排布的最长子字符串
题目描述
解题报告
看到字符串的东西了，心里的想法就不要离开哈希表太远了。
可以用数组模拟哈希表，比如a[3]的数值是5，就可以表示索引是3的字符有5个。
当然，也可以直接使用C++为咱们造好的轮子。
关于这个容器，是有好几个了，因为确实也比较常用，我抽个时间啃一下源码，把捋清楚。
元素按字典序排列需要比较新元素和窗口中元素的字典序，
5个元音字母必须全部出现可以使用一个set来统计窗口中字符的种类，种类满足五个了，就是符合要求了。
至于滑动窗口的逻辑了，就是判断当前是否还是处于升序。
倘若还是升序并且右指针没有达到端点，就滑动右指针去拓展这个窗口
倘若不是升序了，就得调整左指针了。
参考代码(C++版本)
class Solution { public: int longestBeautifulSubstring(string word) { int n = word.size(); if(n < 5) return 0; //开一个存字符类型的哈希表 unordered_set<char> st; int ans = 0;//统计最长的字符串数量 st.insert(word[0]); char tmp = word[0]; int l = 0,r = 1; while(r < n) { //不再满足aeiou的升序 if(tmp > word[r]) { //倘若满足要求，进行统计 if(st.size() == 5) ans = max(ans,r-l); //无论如何，都清空当前这轮哈希表 st.clear(); //移动左端口，进行下一次滑动 l = r; } tmp = word[r]; st.insert(word[r]); //滑动右端口 r ++; } //如果最后到右端点都是aeiou的升序 // cout << "此时的r = " << r <<",l=" << l<<endl; if(st.size() == 5) ans = max(ans,r-l); return ans; } };
总结
① 对滑动窗口的理念有个大致的了解，知道滑动窗口这种形象化的说法，并不是真的有个窗口在滑嗷~
在这里插入图片描述
② 就今天的题而言，滑窗和字符串结合的题还是蛮多的，字符串了，可以直接比较，也可以映射或者结合哈希表来处理的
③ 感觉双指针和滑窗，有点小相似的味道
