【Leetcode Daily】LeetcodeDailySummary-滑动窗口小结
类别
该算法主要分为定长滑动窗口和不定长滑动窗口，前者由于窗口大小固定，往往是来求窗口内某种极值，极大、极小或者其它事物，后者则专注于求子数组/子字符串的数量。
不定长滑动窗口有的会尽可能追求窗口长度的极值，又会因为题目，细分几个种类，比如越长越满足、越短月满足，或者刚好满足的情况。
定长滑动窗口
基本的思路是，先是初始化一个定长的窗口，初始化到窗口长度减一，然后在循环过程中，先加入新元素，达到窗口满足大小的情况，然后自行检查窗口是否满足题目条件，并更新记录数值。随后退出最旧的元素。
示例题目与更为详细的思路讲解在博客 【Leetcode Daily】1456定长子串中元音的最大数目
不定长滑动窗口
与定长滑动窗口的不同之处在于，不需要开始先把窗口调整至某个状态，只需要不断地加入元素，检查条件，然后在不满足条件时，持续退出旧元素，直到再次满足条件。
至于几种分类，对于求满足条件窗口长度，只要每次循环持续更新记录数值的最大或最小就好，像是博客 【Leetcode Daily】2904最短且字典序最小的美丽子字符串。
而子数组长度，对于越长越合法类型，相当于遍历右节点，统计左节点的可能，每次满足条件，就直接加上左节点的下标值到结果上，因为该左节点与其更左的节点下标都一定会满足，“越长越合法”嘛，比如博客 【Leetcode Daily】1358包含所有三种字符的子字符串数目；
于此相对，“越短越合法”则是满足条件后，给结果累计 right-left+1 的下标，比如博客 【Leetcode Daily】713乘积小于K的子数组
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！
相关推荐
2025-04-24
【Leetcode Daily】1052爱生气的书店老板
题目浅析 想查看原题可以点击题目链接。 简单地说，就是给两个整型数组，以及一个整数 minutes，按某个要求（具体看原题，难以简化），求一个数组在另一个数组和 minutes 约束下的求的最大值。 思路分享 陆爻齐的思路是计算窗口内（也就是冷静的分钟）不满意生气离开的最大值，加上不生气的心情值，再减去所有生气离开的数值得出答案，但由于思想复杂了点，所以略微修改模板结构，也就是下面陆爻齐的答案。 参照灵茶山艾府，其实只要区分开两部分相加即可，然后直接参照模板。这两部分，一个是不生气的值，一个是生气下的值，取生气下最大值即可。这样就不用像上面一样多一次运算。 https://leetcode.cn/problems/grumpy-bookstore-owner/solutions/2751888/ding-chang-hua-dong-chuang-kou-fu-ti-dan-rch7/ 代码解答（强烈建议自行解答后再看） 陆爻齐的解法 12345678910111213141516171819202122232425class Solution...
2025-04-28
【Leetcode Daily】1297子串的最大出现次数
题目浅析 想查看原题可以点击题目链接。 简单地说，就是给一个字符串，求满足要求的子串中，出现最多的次数。该要求为 1. 内部的字母数量小于 maxLetters；2. 整个字符串的长度在 minSize 和 maxSize 之间（闭区间）。 思路分享 该题的难度在于干扰项 maxSize，由于求子串尽可能多的出现，所以该子串的长度必然越小越好，就是 minSize。 就是定长滑动窗口(【Leetcode Daily】1456定长子串中元音的最大数目)，有了个字母数量不大于 maxLetters 的限制，再用哈希统计满足要求字符串出现的次数即可。 代码解答（强烈建议自行解答后再看） 陆爻齐的解法 1234567891011121314151617181920212223242526272829class Solution {public: int maxFreq(string s, int maxLetters, int minSize, int maxSize) { vector<int>...
2025-04-23
【Leetcode Daily】1423可获得的最大点数
题目浅析 想查看原题可以点击题目链接。 简单地说，就是给一个整型数组和一个数字 k，求按照某种方式下获取卡牌所得的最大点数。该方式为每次只能够取得最左或者最右的卡牌。 思路分享 逆向思路，由于每次拿卡牌只拿两侧，所以中间部分是连续的，可以视为一个定长滑动窗口，只不过是求窗口内的最小和，通过这个数值得到答案。滑动窗口模板沿用【Leetcode Daily】1456定长子串中元音的最大数目 正向思路，穷举所有组合可能。 https://leetcode.cn/problems/maximum-points-you-can-obtain-from-cards/solutions/2551432/liang-chong-fang-fa-ni-xiang-si-wei-zhen-e3gb/ 代码解答（强烈建议自行解答后再看） 逆向 12345678910111213141516171819202122232425class Solution {public: int maxScore(vector<int>& cardPoints,...
2025-04-18
【Leetcode Daily】1343大小为K且平均值大于等于与之的子数组数目
题目浅析 想查看原题可以点击题目链接。 简单地说，就是给一个整数数组，两个整数 threshold 和 k。k是限定子数组的长度，threshold 是阈值。求这个数组中长度为 k 且平均值大于阈值 threshold 的数目。 注意，在算法题中，子数组默认连续，而子序列默认不连续。 思路分享 定长滑动窗口模板秒了,具体参照 【Leetcode Daily】1456定长子串中元音的最大数目 不过这里的和用 int 也没问题，我估计是因为是大于等于阈值这个条件的关系，大于的情况即使因为整数的小数丢失，也能算做等于情况计入。 代码解答（强烈建议自行解答后再看） 滑动窗口 1234567891011121314151617181920class Solution {public: int numOfSubarrays(vector<int>& arr, int k, int threshold) { int result = 0; int sum = 0; for (int i =...
2025-05-05
【Leetcode Daily】1493删掉一个元素以后全为1的最长子数组
题目浅析 想查看原题可以点击题目链接。 简单地说，就是给一个由 0 和 1 组成的数组，现在需要从中删除一个元素，求删除后只含 1 的最长子数组长度。 思路分享 除了不定长滑动窗口模板的内容（【Leetcode Daily】3090每个字符最多出现两次的最长字符串），本题只有一点需要特别注意，那就是必须要删除一个字符的需求。 由于这个需求的存在，会造成一种情况，如果子串内没有 0，也必须删除一个字符，而如果子串内有一个 0，那就删除 0 来获取长度。所以可以发现，无论是什么情况，最后求得的结果都要减一。 代码解答（强烈建议自行解答后再看） 陆爻齐的解法 12345678910111213141516171819202122class Solution {public: int longestSubarray(vector<int>& nums) { int zero_count = 0; int left = 0; int n = nums.size(); int...
2025-04-14
【Leetcode Daily】1534统计好三元组
题目浅析 想查看原题可以点击题目链接。 简单地说，就是给一个数组，要求统计其中所有满足要求三元组的数量。该要求是，两两之差，满足题目的三个数字。 思路分享 首先就是暴力解法，O(n^3)，不过陆爻齐在普通的暴力上做了一点点剪枝，但终究还是暴力。 想要比较好的完成本题，就需要学习前缀和，总体的思路是固定三元组中的两个，通过要求来求得剩下一个值的范围，将该范围在前缀和中搜寻，符合则找到合适的三元组。 https://leetcode.cn/problems/count-good-triplets/?envType=daily-question&envId=2025-04-14 代码解答（强烈建议自行解答后再看） 陆爻齐小改良的暴力解法 12345678910111213141516171819class Solution {public: int countGoodTriplets(vector<int>& arr, int a, int b, int c) { int size =...
系列文章