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

滑动窗口：定长滑动窗口与不定长滑动窗口

news 2026/6/10 12:59:09

此文是对于前文滑动窗口的补充：LeetCode 滑动窗口个人思路详解-CSDN博客

定长滑动窗口

先由一道题来引入我们的定长滑动窗口

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

我这里给出两种解题方法：

class Solution { public: int maxVowels(string s, int k) { int ret = 0,count = 0; int n = s.size(); int left = 0; for(int right = 0;right<n;right++) { char in = s[right]; if(in=='a'||in=='e'||in=='i'||in=='o'||in=='u') { count++; } while(right-left+1>k) { char out = s[left]; if(out=='a'||out=='e'||out=='i'||out=='o'||out=='u') { count--; } left++; } ret = max(ret,count); } return ret; } };

class Solution { public: int maxVowels(string s, int k) { int ret = 0,count = 0; int n = s.size(); for(int i = 0;i<n;i++) { if(s[i]=='a'||s[i]=='e'||s[i]=='i'||s[i]=='o'||s[i]=='u') { count++; } int left = i-k+1; if(left<0) continue; ret = max(ret,count); if(s[left]=='a'||s[left]=='e'||s[left]=='i'||s[left]=='o'||s[left]=='u') { count--; } } return ret; } };

第二段代码在内存消耗和AC时间上更有优势，第一种写法跟我之前的滑动窗口固定模板写法一致
接下来我们总来总结一下第二种写法的模板

套路模板：

窗口右端点在 i 时，由于窗口长度为 k，所以窗口左端点为 i−k+1。

这里我们三步走：入-更新答案-出（精华所在）

入：下标为 i 的元素进入窗口，更新相关统计量（本题为窗口内的元音个数）。如果窗口左端点 i−k+1<0，说明尚未形成第一个窗口，重复第一步。
更新答案：此时窗口长度为 k，符合题目要求，用相关统计量（本题为窗口内的元音个数）更新答案。
出：下标为 i−k+1 的元素离开窗口，更新相关统计量（本题为窗口内的元音个数），为下一个循环做准备。注：元素离开窗口后，窗口长度为 k−1。下一轮循环元素进入窗口后，窗口长度为 k。

答疑
问：为什么窗口右端点为 i 的时候，左端点是 i−k+1？

答：对于窗口（闭区间）[L,R] 来说，[L,R] 里面的元素个数为 R−L+1。比如 [2,5] 里面有 2,3,4,5 一共 5−2+1=4 个数。如果窗口长度为 k，即 R−L+1=k，解得 L=R−k+1。所以右端点为 R 的时候，左端点为 R−k+1。

下面来解决几道问题：

643. 子数组最大平均数 I - 力扣（LeetCode）

class Solution { public: double findMaxAverage(vector<int>& nums, int k) { int n = nums.size(); int ret = INT_MIN,sum = 0; for(int i = 0;i<n;i++) { sum+=nums[i]; int left = i-k+1; if(left<0) continue; ret = max(ret,sum); sum-=nums[left]; } return(double)ret/k; } };

1343. 大小为 K 且平均值大于等于阈值的子数组数目 - 力扣（LeetCode）

class Solution { public: int numOfSubarrays(vector<int>& arr, int k, int threshold) { int n = arr.size(); int count = 0,sum = 0; for(int i = 0;i<n;i++) { sum+=arr[i]; int left = i-k+1; if(left<0) continue; if(sum>=threshold*k) count++; sum-=arr[left]; } return count; } };

2090. 半径为 k 的子数组平均值 - 力扣（LeetCode）

class Solution { public: vector<int> getAverages(vector<int>& nums, int k) { int n=nums.size();long long sum=0; vector<int>args(n,-1); for( int i=0;i<n;i++) { sum+=nums[i]; if(i<2*k) continue;//未达到2K➕1 args[i-k] = sum/(2*k+1);//更新位置为右端点减去K个单位的位置 sum-=nums[i-2*k];//离开窗口的左端点为右端点减掉区间长度 } return args; } };

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

class Solution { public: int minimumRecolors(string blocks, int k) { int ret=k; int count=0; for(int i=0;i<blocks.size();i++) { if(blocks[i]=='W') count++; int left = i-k+1; if(left<0) continue; ret= min(ret,count); if(blocks[left]=='W') count--; } return ret; } };

2841. 几乎唯一子数组的最大和 - 力扣（LeetCode）

class Solution { public: long long maxSum(vector<int>& nums, int m, int k) { int n=nums.size(); long long sum=0,ret=0; unordered_map<int,int> Countmap; for(int i=0;i<n;i++) { sum+=nums[i]; Countmap[nums[i]]++; int left = i-k+1; if(left<0) continue; if(Countmap.size()>=m) ret=max(ret,sum); int out=nums[left]; sum-=out; if(--Countmap[out]==0) Countmap.erase(out); } return ret; } };

1423. 可获得的最大点数 - 力扣（LeetCode）

class Solution { public: int maxScore(vector<int>& cardPoints, int k) { int AllSum = 0; for(auto&e:cardPoints) { AllSum+=e; } if(k==cardPoints.size()) return AllSum; long long sum = 0,ret = INT_MAX; for(int right = 0;right<cardPoints.size();right++) { sum+=cardPoints[right]; int left = right-(cardPoints.size()-k)+1; if(left<0) continue; ret = min(sum,ret); sum-=cardPoints[left]; } return AllSum-ret; } };

1052. 爱生气的书店老板 - 力扣（LeetCode）

class Solution { public: int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) { int OriginSum = 0; for(int i = 0;i<customers.size();i++) { if(grumpy[i]==0) OriginSum+=customers[i]; } long NewSum = 0,ret = 0; for(int right = 0;right<customers.size();right++) { if(grumpy[right]==1) NewSum+=customers[right]; int left = right-minutes+1; if(left<0) continue; if(NewSum>ret) ret = max(ret,NewSum); if(grumpy[left]==1) NewSum-=customers[left]; } return OriginSum+ret; } };

3679. 使库存平衡的最少丢弃次数 - 力扣（LeetCode）

class Solution { public: int minArrivalsToDiscard(vector<int>& arrivals, int w, int m) { unordered_map<int, int> cnt; int ret = 0; int n = arrivals.size(); vector<int> keep(n, 0); // keep[i] = 1 表示这个位置的物品被保留 for (int i = 0; i < n; i++) { int x = arrivals[i]; // 如果当前窗口中 x 已经有 m 个，就丢弃当前物品 if (cnt[x] == m) { ret++; } else { cnt[x]++; keep[i] = 1; } // 维护窗口大小，移除 i-w+1 这个位置 int left = i - w + 1; if (left >= 0 && keep[left]) { cnt[arrivals[left]]--; } } return ret; } };

上述一些题目需要涉及到对题意的转换，记住如果使用滑动窗口，我们需要元素为0或者正整数，不能出现负数