【题目讲解】 算法系列之定长类滑动窗口解析（上）

目录前言Part1. 标准滑动窗口Part1.1. 定长子串中元音的最大数目Part1.2. 子数组的最大平均数Part2. 滑动窗口哈希表Part2.1. 长度为K子数组中的最大和Part3. 转化类滑动窗口Part3.1. 得到K个黑块的最少涂色次数Part3.2. 重新安排会议得到最多空闲时间Part4. 总结Part5. 结语前言滑动窗口作为经典的算法之一他可以有效地简化遍历这个操作的时间复杂度。接下来跟随小编的步伐来看看这个算法具体使用吧。lets go!!!!!!!!!Part1. 标准滑动窗口我们先来看标准的滑动窗口的实施理解这个基础才可以更好的去结合一些花里胡哨的东西。我们来看看吧Part1.1. 定长子串中元音的最大数目题目链接1456. 定长子串中元音的最大数目 - 力扣LeetCode我们首先想到的方法就是把这个字符串中长度为三的串全部处理一遍得到元音数目的最大值但这样对于这个字符串每个字符都几乎要遍历三次有没有一次遍历就可以解决问题的方法有的那就是滑动窗口我们来看这里的关键就在于保留了之前遍历的成果即1~2中字符是否为元音的信息只改变最少要改变的即必须要知道3处的字符的信息才能继续遍历同时要满足题目的条件即m定长也就是我没必要删去0处字符曾经的影响即他如果是个元音字符我们就要num--来消除他的影响使得m在逻辑上的长度不变我们在用一个max_num来记录全局的最大值作为我们的最终答案我们来看代码class Solution { public: bool is_vowel(char a)//判断是否为元音字符 { if(aa||ae||ai||ao||au) { return true; } return false; } int maxVowels(string s, int k) { int max_num0; int num0; for(int i0;ik;i)//初始化窗口 算出num的初始值 { if(is_vowel(s[i])) { num; } } max_numnum;//初始化全局最大值 int left0;//窗口的最左边 指向要抛弃的元素的下标 int rightk;//窗口的最右边 指向要新增的元素的下标 while(rights.size()) { if(is_vowel(s[left]))//如果是元音 就要去除他造成的影响 { num--; } if(is_vowel(s[right]))//看看新增的字符是否为元音 是就加上 { num; } if(nummax_num)//更新全局最大值 { max_numnum; } left;//窗口滑动到下一个要抛弃的元素 right;//窗口滑动到下一个要新增的元素 } return max_num; } };这就是标准滑动窗口的实施了我们再看一题来巩固一下吧。Part1.2. 子数组的最大平均数题目链接643. 子数组最大平均数 I - 力扣LeetCode直接来看代码class Solution { public: double findMaxAverage(vectorint nums, int k) { double num0;//记录窗口内所有元素的和由于窗口的长度是一定的 我们只要记录所有元素和就可以知道平均数了 double max_average0; for(int i0;ik;i) { numnums[i];//初始化 } max_averagenum/k;//初始化记录全局最大平均数的变量 int left0;//指向要抛弃的元素 int rightk;//指向要新增的元素 while(rightnums.size()) { numnums[right];//加上后面新增的元素的值 num-nums[left];//这里去除前面的影响就是删去num中前面元素的值 if(num/kmax_average) { max_averagenum/k;//更新最值 } right;//移动窗口 left; } return max_average; } };这就是标准滑动窗口我们来看它的一个变种即与哈希表结合。Part2. 滑动窗口哈希表这也算是一种经典的结合即我们在处理的过程中不是记录这些数的总数值什么的而是其出现的频率。我们结合题目来具体看看吧Part2.1. 长度为K子数组中的最大和题目链接2461. 长度为 K 子数组中的最大和 - 力扣LeetCode这道题在之前的基础上还要求我们子数组中所有元素都不能相同这个数组的和才能算是有效的这就需要我们结合哈希思想来解决即我们记录每个元素出现的频率只有每个元素出现都恰好为一时这个数组的和才能参与到最大数组和的更新中我们来看代码class Solution { public: int is_same(vectorshort hash,int i,int a)//根据元素的频率 返回不同的值 { int return_num0;//return_num先初始化为0 if(hash[i]1)//如果此时频率恰好为1 又由于我们一定会对其改变 所以我们要收回之前这个元素出现的频率恰好为一时加的1 return_num-1;//更新为-1 if(a1)//频率处理 hash[i]; else hash[i]--; if(hash[i]1)//如果频率恰好为一 则要返回1 return_num1; return return_num; } long long maximumSubarraySum(vectorint nums, int k) { int minINT_MAX; int maxINT_MIN; for(int i0;inums.size();i) { if(nums[i]max) maxnums[i]; if(nums[i]min) minnums[i]; } vectorshort hash(max-min1,0);//初始化哈希 int dif_num0;//记录子数组中不同元素的数目即dif_numm时 这个数组和有效 long long max_num0;//记录全局最大值 long long num0;//记录过程数组和 int left0; int rightk; for(int i0;ik;i)//初始化num dif_num { numnums[i]; dif_numis_same(hash,nums[i]-min,1); } if(dif_numk)//当dif_numk时 更新最值 { max_numnum; } while(rightnums.size()) { num-nums[left];//去除 numnums[right];//新增 dif_numis_same(hash,nums[left]-min,2);//去除 dif_numis_same(hash,nums[right]-min,1);//新增 if(dif_numkmax_numnum)//当两个条件都满足时 更新最值 { max_numnum; } left;//移动滑窗 right; } return max_num; } };这种题就是在数据的处理上用到了哈希表结合常规知识我们来看下一题Part3. 转化类滑动窗口有时候我们这个题目不是明显的说这个子数组是明显的我们就需要转化问题变成滑动窗口我们来看Part3.1. 得到K个黑块的最少涂色次数题目链接2379. 得到 K 个黑块的最少涂色次数 - 力扣LeetCode我们来看图解我们来看代码class Solution { public: int is_white(char c)//判断是不是白块 { if(cW) return 1; else return 0; } int minimumRecolors(string blocks, int k) { int left0; int rightk; int num0; for(int i0;ik;i) { numis_black(blocks[i]);//初始化num } int minnum;//初始化全局最小值 while(rightblocks.size()) { num-is_black(blocks[left]);//去除前面的 numis_black(blocks[right]);//增加后面的 if(nummin) { minnum;//更新最小值 } } return min; } };这样我们就解决了这题很多题他不是明着来滑动窗口的他是潜藏在其中的在下一题也有体现我们来看Part3.2. 重新安排会议得到最多空闲时间题目链接3439. 重新安排会议得到最多空余时间 I - 力扣LeetCode我们来看图解我们来看代码class Solution { public: int maxFreeTime(int eventTime, int k, vectorint startTime, vectorint endTime) { vectorint arr; if(startTime[0]!0) arr.push_back(startTime[0]-0); for(int i1;istartTime.size();i) { arr.push_back(startTime[i]-endTime[i-1]);//得到空闲时间数组 } if(eventTime!endTime[endTime.size()-1]) arr.push_back(eventTime-endTime[endTime.size()-1]); int sizek1;//得到窗口长度 int num0;//下面就是正常求最值 int max_num0; for(int i0;isize;i) { if(iarr.size()) return num; numarr[i]; } max_numnum; int left0; int rightk1; while(rightarr.size()) { num-arr[left]; numarr[right]; if(nummax_num) max_numnum; } return max_num; } };经过转化我们将原本离散的场景整合为连续的场景从而可以使用滑动窗口来解决。Part4. 总结滑动窗口本质上还是一个工具主要就是帮我们解决在连续的条件下直接遍历的时间复杂度过高的场景。它可以大大简化时间复杂度用一句话总结就是“拆东墙补西墙”保留之前花费时间得来的成果改变需要改变的。其实通过上面的代码我们也可以发现一套代码的通用模板我们来看int main() { { ;//定义变量 } { ;//初始化变量将窗口展开 } { ;//看条件是否初始化全局类型的值 } while(){ { ;//去除左边 } { ;//新增右边 } { ;//更新最值 } { ;//移动窗口 } } //。。。。。。。 }Part5. 结语相信通过上面几道题的讲解大家已经对这个算法有了一定程度的认识后续小编还会推出下篇更加深化滑动窗口的相关知识敬请期待~~希望这篇博客可以给大家带来帮助。最后祝大家可以春风得意马蹄疾一日看尽长安花最后的最后要是觉得本文还可以的话可以点点赞关注小编一波谢谢大家~