定长滑动窗口---初阶篇

滑动窗口核心思想

定长滑动窗口套路

定长滑动窗口习题剖析

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

643. 子数组最大平均数 I

1343. 大小为 K 且平均值大于等于阈值的子数组数目

2090. 半径为 k 的子数组平均值

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

2841. 几乎唯一子数组的最大和

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

1423. 可获得的最大点数

1052. 爱生气的书店老板

1652. 拆炸弹

总结

此篇博客将对定长滑动窗口这一算法进行深度剖析，会结合灵神的算法题单对每个题目进行解析。本篇博客中的所有题目均来自于灵茶山艾府 - 力扣（LeetCode）分享的题单。

滑动窗口核心思想

根据名称可以看出滑动窗口有两个性质：1）窗口，说明其是密闭的，必定有左右两个边界；2）滑动，说明其左右边界是在动态变化的。

定长滑动窗口常用于解决求连续的个数问题。

下面通过一个例题对滑动窗口问题进行更深一步的分析。

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

题目：给定一个字符串，求连续元音字母的最大个数。

思路一：通过暴力枚举，以一个位置为起点，向后看k个字符中有多少个元音字符，其时间复杂度是O(N^2)，在这题中是会出现超时的。

思路二：对思路一进行优化。可以看出在进行k个字符的查找时，如果按照思路一进行会出现很多多余的步骤，比如：abc查找后，对bci重新进行查找，此时bc就出现了重复累加的操作；这一步骤就可以简化为将头部字符删去，在尾部新增字符。

定长滑动窗口套路

定长滑动窗口分为三步：进窗口---更新答案---出窗口。

进窗口和出窗口均是为了让窗口满足提议要求，在进出窗口之间对答案进行更新，调整。

定长滑动窗口习题剖析

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

题解：通过left和right两个指针来时刻维持窗口大小在k范围以内，用tmp来记录当前窗口元音字符的个数。

class Solution {
public:int maxVowels(string s, int k) {//通过left和right来控制窗口的左右边界int n=s.size();int left=0,right=0;unordered_set<char> vowel={'a','e','i','o','u'};   //保存元音字符int ret=0,tmp=0;  //ret用来记录最大数目，即返回值，tmp用于记录每k个字符中元音个数while(right<n){while(right-left<k){//将窗口填满if(vowel.count(s[right++])) tmp++;}//此时窗口已经填满，对结果进行更新ret=max(ret,tmp);//让窗口向右走if(vowel.count(s[left++])) tmp--;}return ret;}
};

643. 子数组最大平均数 I

题解：定长滑动窗口类题型的套路都比较类似，使用左右指针维护窗口，用一个变量来记录窗口内的结果。

class Solution {
public:double findMaxAverage(vector<int>& nums, int k) {int n=nums.size();int left=0,right=0;  //通过左右指针来维护窗口double ret=INT_MIN ;  //此处不能再将ret置为0了，因为nums中数据可能为负数，再对ret取小的时候会出现错误int tmp=0;  while(right<n){//将数据进窗口while(right-left<k)tmp+=nums[right++];  //用tmp来记录窗口类数据之和ret=max(ret,tmp/(double)k);   //更新答案//让窗口向后移动tmp-=nums[left++];}return ret;}
};

1343. 大小为 K 且平均值大于等于阈值的子数组数目

题解：与前两题异曲同工之妙。

class Solution {
public:int numOfSubarrays(vector<int>& arr, int k, int threshold) {int n=arr.size();int left=0,right=0;int count=0,tmp=0;  //count用来计数，tmp记录每个区间的总和while(right<n){//入窗口while(right-left<k)tmp+=arr[right++];//对答案进行更新if(tmp/k>=threshold) count++;//出窗口tmp-=arr[left++];}return count;}
};

2090. 半径为 k 的子数组平均值

题解：以i为下标，半径是k的平均值，相当于一个2*k长度的动态窗口的平均值。

class Solution {
public:vector<int> getAverages(vector<int>& nums, int k) {int n=nums.size();vector<int> ret(n,-1);   //ret作为返回值，将ret数组均初始化为-1来解决左右两边元素不足的问题if(k==0) return nums;   //对特殊情况处理if(n<=2*k) return ret;   //当k值较大的时候，就不需要进入循环了int left=0,right=0;long long tmp=0;      //注意：此处需要使用long long，因为测试用例比较恶心使用int会已出while(right<n){//入窗口while(right<n&&right-left+1<=2*k+1)tmp+=nums[right++];//对答案进行更新int mid=(right-1+left)/2;ret[mid]=tmp/(2*k+1);//出窗口tmp-=nums[left++];}return ret;}
};

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

题解：通过滑动窗口，每次记录窗口内达到要求需要涂色的个数。

class Solution {
public:int minimumRecolors(string blocks, int k) {int n=blocks.size();int left=0,right=0;int ret=INT_MAX,tmp=0;  //此处不能将ret取作0，因为在对ret取小的时候0会一直是最小的while(right<n){//入窗口while(right-left<k)if(blocks[right++]=='W') tmp++;//更新结果ret=min(ret,tmp);//出窗口if(blocks[left++]=='W') tmp--;}return ret;}
};

2841. 几乎唯一子数组的最大和

题解：此题要记录一个元素是否唯一，所以可以采用哈希表来记录数据时候出现过。

class Solution {
public:long long maxSum(vector<int>& nums, int m, int k) {int n=nums.size();int left=0,right=0;unordered_map<int,int> record;   //记录数据出现了几次int count=0;  //count记录不相同元素个数long long tmp=0,ret=0;     //此题tmp和ret需要使用long long防止越界 while(right<n){//入窗口while(right-left<k){tmp+=nums[right];if(record[nums[right]]==0) count++;  //还没有该元素record[nums[right]]++;right++;}//调整结果前还需要判断区间是否可取，即是否几乎唯一if(count>=m) ret=max(ret,tmp);//出窗口if(record[nums[left]]==1) count--;record[nums[left]]--;tmp-=nums[left++];}return ret;}
};

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

题解：此题类似于上一题的变形，此题对答案更新是有条件的，需要保证每个元素各不相同。

class Solution {
public:long long maximumSubarraySum(vector<int>& nums, int k) {int n=nums.size();int left=0,right=0;unordered_map<int,int> record;   //记录元素出现的此处int count=0;   //记录重复元素个数long long ret=0,tmp=0;while(right<n){//入窗口while(right-left<k){if(record[nums[right]]==1) count++;record[nums[right]]++;tmp+=nums[right++];}//调整结果if(count==0) ret=max(ret,tmp); //出窗口if(record[nums[left]]==2) count--;record[nums[left]]--;tmp-=nums[left++];}return ret;}
};

1423. 可获得的最大点数

题解：求左右两边和的最大值------>求中间部分和的最小值。

class Solution {
public:int maxScore(vector<int>& cardPoints, int k) {//此题可以转化为滑动窗口问题，求左右两边的最大值，就转化为了求中间部分的最小值int n=cardPoints.size();int num=n-k;   //计算出要求中间元素和的个数int left=0,right=0;int ret=INT_MAX,tmp=0;int sum=0;   //求数组总和for(auto e:cardPoints) sum+=e; while(right<n){//入窗口while(right-left<num)tmp+=cardPoints[right++];//调整答案ret=min(ret,tmp);//出窗口tmp-=cardPoints[left++];}return sum-ret;}
};

1052. 爱生气的书店老板

题解：要将则几分钟的利用最大化，即让这一区间内的客人总和最多即可。

class Solution {
public:int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {int n=customers.size();int sum=0;  //先求出，不生气情况下的客人总量for(int i=0;i<n;i++)if(grumpy[i]==0) sum+=customers[i];//将抑制生气的利益最大化，求出minutes区间中生气是客户最大值int ret=0,tmp=0;int left=0,right=0;while(right<n){//入窗口while(right-left<minutes){if(grumpy[right]) tmp+=customers[right];right++;}//更新答案ret=max(ret,tmp);//出窗口if(grumpy[left])tmp-=customers[left];left++;}return ret+sum;   }
};

1652. 拆炸弹

题解：对于k==0的情况直接返回空数组即可，对于k>0的情况，从0位置向后进行滑动窗口；对于k<0的情况，从n-1位置向前进行滑动窗口。

class Solution {
public:vector<int> decrypt(vector<int>& code, int k) {int n=code.size();vector<int> ret(n);if(k==0) return ret;else if(k>0){//对于k>0的情况，从0位置开始向后使用滑动窗口int left=1,right=1,i=0;int tmp=0;while(i<n){//入窗口while((right+n-left)%n<k){tmp+=code[right++];right%=n;}//调整答案ret[i++]=tmp;//出窗口tmp-=code[left++];left%=n;}}else  //k<0{//从n-1位置向前使用滑动窗口int left=n-2,right=n-2,i=n-1;int tmp=0;while(i>=0){//入窗口while((right+n-left)%n<-k){tmp+=code[left--];left=(left+n)%n;}//调整答案ret[i--]=tmp;//出窗口tmp-=code[right--];right=(right+n)%n;}}return ret;}
};