当前位置：首页 > news >正文

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

news 2026/6/26 3:31:40

前言

Part1. 标准滑动窗口

Part1.1. 定长子串中元音的最大数目

Part1.2. 子数组的最大平均数

Part2. 滑动窗口+哈希表

Part2.1. 长度为K子数组中的最大和

Part3. 转化类滑动窗口

Part3.1. 得到K个黑块的最少涂色次数

Part3.2. 重新安排会议得到最多空闲时间

Part4. 总结

Part5. 结语

前言

滑动窗口作为经典的算法之一，他可以有效地简化遍历这个操作的时间复杂度。接下来，跟随小编的步伐来看看这个算法具体使用吧。
let's go!!!!!!!!!

Part1. 标准滑动窗口

我们先来看标准的滑动窗口的实施，理解这个基础，才可以更好的去结合一些花里胡哨的东西。我们来看看吧：

Part1.1. 定长子串中元音的最大数目

题目链接：1456. 定长子串中元音的最大数目 - 力扣（LeetCode）

我们首先想到的方法就是把这个字符串中长度为三的串全部处理一遍，得到元音数目的最大值，但这样对于这个字符串每个字符都几乎要遍历三次，有没有一次遍历就可以解决问题的方法？有的，那就是滑动窗口，我们来看：
这里的关键就在于保留了之前遍历的成果（即1~2中字符是否为元音的信息），只改变最少要改变的（即必须要知道3处的字符的信息，才能继续遍历），同时要满足题目的条件（即m定长，也就是我没必要删去0处字符曾经的影响，即他如果是个元音字符，我们就要num--来消除他的影响，使得m在逻辑上的长度不变），我们在用一个max_num来记录全局的最大值作为我们的最终答案，我们来看代码：
class Solution { public: bool is_vowel(char a)//判断是否为元音字符 { if(a=='a'||a=='e'||a=='i'||a=='o'||a=='u') { return true; } return false; } int maxVowels(string s, int k) { int max_num=0; int num=0; for(int i=0;i<k;i++)//初始化窗口 算出num的初始值 { if(is_vowel(s[i])) { num++; } } max_num=num;//初始化全局最大值 int left=0;//窗口的最左边 指向要抛弃的元素的下标 int right=k;//窗口的最右边 指向要新增的元素的下标 while(right<s.size()) { if(is_vowel(s[left]))//如果是元音 就要去除他造成的影响 { num--; } if(is_vowel(s[right]))//看看新增的字符是否为元音 是就加上 { num++; } if(num>max_num)//更新全局最大值 { max_num=num; } left++;//窗口滑动到下一个要抛弃的元素 right++;//窗口滑动到下一个要新增的元素 } return max_num; } };

这就是标准滑动窗口的实施了，我们再看一题来巩固一下吧。

Part1.2. 子数组的最大平均数

题目链接：643. 子数组最大平均数 I - 力扣（LeetCode）

直接来看代码：

class Solution { public: double findMaxAverage(vector<int>& nums, int k) { double num=0;//记录窗口内所有元素的和（由于窗口的长度是一定的 我们只要记录所有元素和就可以知道平均数了） double max_average=0; for(int i=0;i<k;i++) { num+=nums[i];//初始化 } max_average=num/k;//初始化记录全局最大平均数的变量 int left=0;//指向要抛弃的元素 int right=k;//指向要新增的元素 while(right<nums.size()) { num+=nums[right];//加上后面新增的元素的值 num-=nums[left];//这里去除前面的影响就是删去num中前面元素的值 if(num/k>max_average) { max_average=num/k;//更新最值 } right++;//移动窗口 left++; } return max_average; } };

这就是标准滑动窗口，我们来看它的一个变种，即与哈希表结合。

Part2. 滑动窗口+哈希表

这也算是一种经典的结合，即我们在处理的过程中不是记录这些数的总数值什么的，而是其出现的频率。我们结合题目来具体看看吧：

Part2.1. 长度为K子数组中的最大和

题目链接：2461. 长度为 K 子数组中的最大和 - 力扣（LeetCode）

这道题在之前的基础上还要求我们子数组中所有元素都不能相同，这个数组的和才能算是有效的，这就需要我们结合哈希思想来解决，即我们记录每个元素出现的频率，只有每个元素出现都恰好为一时，这个数组的和才能参与到最大数组和的更新中，我们来看代码：

class Solution { public: int is_same(vector<short>& hash,int i,int a)//根据元素的频率 返回不同的值 { int return_num=0;//return_num先初始化为0 if(hash[i]==1)//如果此时频率恰好为1 又由于我们一定会对其改变 所以我们要收回之前这个元素出现的频率恰好为一时加的1 return_num=-1;//更新为-1 if(a==1)//频率处理 hash[i]++; else hash[i]--; if(hash[i]==1)//如果频率恰好为一 则要返回1 return_num=1; return return_num; } long long maximumSubarraySum(vector<int>& nums, int k) { int min=INT_MAX; int max=INT_MIN; for(int i=0;i<nums.size();i++) { if(nums[i]>max) max=nums[i]; if(nums[i]<min) min=nums[i]; } vector<short> hash(max-min+1,0);//初始化哈希 int dif_num=0;//记录子数组中不同元素的数目（即dif_num==m时 这个数组和有效） long long max_num=0;//记录全局最大值 long long num=0;//记录过程数组和 int left=0; int right=k; for(int i=0;i<k;i++)//初始化num dif_num { num+=nums[i]; dif_num+=is_same(hash,nums[i]-min,1); } if(dif_num==k)//当dif_num==k时 更新最值 { max_num=num; } while(right<nums.size()) { num-=nums[left];//去除 num+=nums[right];//新增 dif_num+=is_same(hash,nums[left]-min,2);//去除 dif_num+=is_same(hash,nums[right]-min,1);//新增 if(dif_num>=k&&max_num<num)//当两个条件都满足时 更新最值 { max_num=num; } left++;//移动滑窗 right++; } return max_num; } };

这种题就是在数据的处理上用到了哈希表结合常规知识，我们来看下一题：

Part3. 转化类滑动窗口

有时候我们这个题目不是明显的说这个子数组是明显的，我们就需要转化问题变成滑动窗口，我们来看：

Part3.1. 得到K个黑块的最少涂色次数

题目链接：2379. 得到 K 个黑块的最少涂色次数 - 力扣（LeetCode）

我们来看图解：

我们来看代码：

class Solution { public: int is_white(char c)//判断是不是白块 { if(c=='W') return 1; else return 0; } int minimumRecolors(string blocks, int k) { int left=0; int right=k; int num=0; for(int i=0;i<k;i++) { num+=is_black(blocks[i]);//初始化num } int min=num;//初始化全局最小值 while(right<blocks.size()) { num-=is_black(blocks[left++]);//去除前面的 num+=is_black(blocks[right++]);//增加后面的 if(num<min) { min=num;//更新最小值 } } return min; } };

这样我们就解决了这题，很多题他不是明着来滑动窗口的，他是潜藏在其中的，在下一题也有体现，我们来看：

Part3.2. 重新安排会议得到最多空闲时间

题目链接：3439. 重新安排会议得到最多空余时间 I - 力扣（LeetCode）

我们来看图解：

我们来看代码：

class Solution { public: int maxFreeTime(int eventTime, int k, vector<int>& startTime, vector<int>& endTime) { vector<int> arr; if(startTime[0]!=0) arr.push_back(startTime[0]-0); for(int i=1;i<startTime.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 size=k+1;//得到窗口长度 int num=0;//下面就是正常求最值 int max_num=0; for(int i=0;i<size;i++) { if(i>=arr.size()) return num; num+=arr[i]; } max_num=num; int left=0; int right=k+1; while(right<arr.size()) { num-=arr[left++]; num+=arr[right++]; if(num>max_num) max_num=num; } return max_num; } };

经过转化，我们将原本离散的场景整合为连续的场景，从而可以使用滑动窗口来解决。

Part4. 总结

滑动窗口本质上还是一个工具，主要就是帮我们解决在连续的条件下直接遍历的时间复杂度过高的场景。它可以大大简化时间复杂度，用一句话总结就是“拆东墙补西墙”，保留之前花费时间得来的成果，改变需要改变的。
其实通过上面的代码，我们也可以发现一套代码的通用模板，我们来看：
int main() { { ;//定义变量 } { ;//初始化变量（将窗口展开） } { ;//看条件是否初始化全局类型的值 } while(){ { ;//去除左边 } { ;//新增右边 } { ;//更新最值 } { ;//移动窗口 } } //。。。。。。。 }