目录
此篇博客将对定长滑动窗口这一算法进行深度剖析，会结合灵神的算法题单对每个题目进行解析。本篇博客中的所有题目均来自于灵茶山艾府 - 力扣（LeetCode）分享的题单。
滑动窗口核心思想
根据名称可以看出滑动窗口有两个性质：1）窗口，说明其是密闭的，必定有左右两个边界；2）滑动，说明其左右边界是在动态变化的。
定长滑动窗口常用于解决求连续的个数问题。
下面通过一个例题对滑动窗口问题进行更深一步的分析。
题目：给定一个字符串，求连续元音字母的最大个数。
思路一：通过暴力枚举，以一个位置为起点，向后看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;
}
};总结
关于定长滑动窗口的初阶篇就到此为止了。滑动窗口问题的问话还是很明显的，当题目出现区间问题是就应该先思考滑动窗口的解法；滑动窗口的套路也是很固定的，就只有三步：入窗口---更新答案---调整窗口。