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

此文是对于前文滑动窗口的补充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;rightn;right) { char in s[right]; if(ina||ine||ini||ino||inu) { count; } while(right-left1k) { char out s[left]; if(outa||oute||outi||outo||outu) { 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;in;i) { if(s[i]a||s[i]e||s[i]i||s[i]o||s[i]u) { count; } int left i-k1; if(left0) 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−k1。这里我们三步走入-更新答案-出精华所在入下标为 i 的元素进入窗口更新相关统计量本题为窗口内的元音个数。如果窗口左端点 i−k10说明尚未形成第一个窗口重复第一步。更新答案此时窗口长度为 k符合题目要求用相关统计量本题为窗口内的元音个数更新答案。出下标为 i−k1 的元素离开窗口更新相关统计量本题为窗口内的元音个数为下一个循环做准备。注元素离开窗口后窗口长度为 k−1。下一轮循环元素进入窗口后窗口长度为 k。答疑问为什么窗口右端点为 i 的时候左端点是 i−k1答对于窗口闭区间[L,R] 来说[L,R] 里面的元素个数为 R−L1。比如 [2,5] 里面有 2,3,4,5 一共 5−214 个数。如果窗口长度为 k即 R−L1k解得 LR−k1。所以右端点为 R 的时候左端点为 R−k1。下面来解决几道问题643. 子数组最大平均数 I - 力扣LeetCodeclass Solution { public: double findMaxAverage(vectorint nums, int k) { int n nums.size(); int ret INT_MIN,sum 0; for(int i 0;in;i) { sumnums[i]; int left i-k1; if(left0) continue; ret max(ret,sum); sum-nums[left]; } return(double)ret/k; } };1343. 大小为 K 且平均值大于等于阈值的子数组数目 - 力扣LeetCodeclass Solution { public: int numOfSubarrays(vectorint arr, int k, int threshold) { int n arr.size(); int count 0,sum 0; for(int i 0;in;i) { sumarr[i]; int left i-k1; if(left0) continue; if(sumthreshold*k) count; sum-arr[left]; } return count; } };2090. 半径为 k 的子数组平均值 - 力扣LeetCodeclass Solution { public: vectorint getAverages(vectorint nums, int k) { int nnums.size();long long sum0; vectorintargs(n,-1); for( int i0;in;i) { sumnums[i]; if(i2*k) continue;//未达到2K➕1 args[i-k] sum/(2*k1);//更新位置为右端点减去K个单位的位置 sum-nums[i-2*k];//离开窗口的左端点为右端点减掉区间长度 } return args; } };2379. 得到 K 个黑块的最少涂色次数 - 力扣LeetCodeclass Solution { public: int minimumRecolors(string blocks, int k) { int retk; int count0; for(int i0;iblocks.size();i) { if(blocks[i]W) count; int left i-k1; if(left0) continue; ret min(ret,count); if(blocks[left]W) count--; } return ret; } };2841. 几乎唯一子数组的最大和 - 力扣LeetCodeclass Solution { public: long long maxSum(vectorint nums, int m, int k) { int nnums.size(); long long sum0,ret0; unordered_mapint,int Countmap; for(int i0;in;i) { sumnums[i]; Countmap[nums[i]]; int left i-k1; if(left0) continue; if(Countmap.size()m) retmax(ret,sum); int outnums[left]; sum-out; if(--Countmap[out]0) Countmap.erase(out); } return ret; } };1423. 可获得的最大点数 - 力扣LeetCodeclass Solution { public: int maxScore(vectorint cardPoints, int k) { int AllSum 0; for(autoe:cardPoints) { AllSume; } if(kcardPoints.size()) return AllSum; long long sum 0,ret INT_MAX; for(int right 0;rightcardPoints.size();right) { sumcardPoints[right]; int left right-(cardPoints.size()-k)1; if(left0) continue; ret min(sum,ret); sum-cardPoints[left]; } return AllSum-ret; } };1052. 爱生气的书店老板 - 力扣LeetCodeclass Solution { public: int maxSatisfied(vectorint customers, vectorint grumpy, int minutes) { int OriginSum 0; for(int i 0;icustomers.size();i) { if(grumpy[i]0) OriginSumcustomers[i]; } long NewSum 0,ret 0; for(int right 0;rightcustomers.size();right) { if(grumpy[right]1) NewSumcustomers[right]; int left right-minutes1; if(left0) continue; if(NewSumret) ret max(ret,NewSum); if(grumpy[left]1) NewSum-customers[left]; } return OriginSumret; } };3679. 使库存平衡的最少丢弃次数 - 力扣LeetCodeclass Solution { public: int minArrivalsToDiscard(vectorint arrivals, int w, int m) { unordered_mapint, int cnt; int ret 0; int n arrivals.size(); vectorint 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-w1 这个位置 int left i - w 1; if (left 0 keep[left]) { cnt[arrivals[left]]--; } } return ret; } };上述一些题目需要涉及到对题意的转换记住如果使用滑动窗口我们需要元素为0或者正整数不能出现负数不定长滑动窗口关于不定长的滑动窗口我在前文已经做了比较详细的解读在这里不进行过多的方法赘述不定长滑动窗口主要分为三类求最长子数组求最短子数组求子数组个数。注滑动窗口相当于在维护一个队列。右指针的移动可以视作入队左指针的移动可以视作出队。相关题目包括越短越合法/求最长/求最大越长越合法/求最短/求最小 以及之后的单序列双指针双序列双指针三指针分支循环因为笔者最近在研究动态规划所以关于之后的滑动窗口的题目需要之后在更新非常抱歉哈哈