基础算法集训到第16天今天专门啃滑动窗口。这个算法名字听起来有点工程化实际上它是处理一类问题的统一套路连续子数组、子串的统计、区间极值、文本匹配几乎所有需要“在某段连续数据范围内找规律”的题都能用滑动窗口把复杂度从O(n*k)一路压到O(n)。我第一次学的时候觉得它不过就是双指针后来刷了几道题才发现真正的难点不在“想到用窗口”而在“窗口什么时候动、动了之后状态怎么维护、答案在哪个时机更新”。这篇文章就把我集训这十几天的理解、踩过的坑、以及几道必刷题目的完整拆解都整理出来给同样在啃这块的朋友当个参考。1. 滑动窗口到底是什么先建立直觉1.1 从暴力解到窗口的演进先看一个最简单的场景给定一个数组求长度为k的连续子数组的最大和。新手第一反应就是两层循环外层枚举起点内层累加k个数复杂度O(n*k)数据量一大就超时。滑动窗口的思路是别每次都从头加窗口从i滑到i1时新增的是nums[ik]离开的是nums[i]所以下一次区间和只需要在上一次的基础上做一次减法、一次加法瞬间把每次更新的代价降到O(1)。用一个生活化类比来理解你站在一扇固定宽度的窗户前看街道。窗框向右滑动一格左边走出视线一个行人右边走进一个新的行人你看到的总人数始终是那么几个但每滑一格的更新成本极低。窗口这个叫法不是因为算法复杂而是因为它真的就是一扇会移动的“取景框”。1.2 窗口的三要素与两个指针所有滑动窗口代码里都有两个核心指针left和right分别代表窗口的左右边界。另外还要有一个“窗口状态”这个状态可以是区间和、字符频次哈希表、最大值、最小值等等它是窗口滑动过程中需要持续维护的核心数据。三个要素缺一不可右指针负责“扩窗口”每轮循环向右移动把新元素纳入状态左指针负责“缩窗口”当窗口不再满足条件时或者为了下一步右移腾出空间时把元素移出状态答案在主循环内某个明确时机更新不能早也不能晚。理解这三件事的分工基本就能解决90%的滑动窗口题目。1.3 题型分类固定窗口与可变窗口滑动窗口大体分成两类。固定窗口大小好说题目直接告诉你窗口宽度比如“长度为k的子数组的平均值”、“每k个连续元素的最大值”。这类题的核心是“进了新值、丢了旧值、更新答案”三步走。可变窗口就复杂一些它没有一个预设的宽度而是通过条件来动态调整比如“和大于等于target的最短子数组”、“包含一个字符串所有字符的最短子串”。这时右指针负责探索左指针负责在满足条件后尽量压缩最终在所有合法窗口中找最优解。类型窗口大小左指针移动时机典型题固定窗口恒定k每次右移后同步右移滑动窗口最大值、子数组最大平均数可变窗口动态变化仅当窗口不满足条件或压缩寻优时长度最小的子数组、最小覆盖子串固定窗口的可读性更强可变窗口对边界条件更敏感也更容易写错。后面我会分别用具体题来拆解。2. 滑动窗口的通用模板一份能直接改的代码骨架2.1 为什么先把模板固定下来刷题有一个很大的误区拿到题立刻开始写具体逻辑写到一半发现窗口的移动时机错了再回头改很浪费时间。我集训时先把一套通用骨架背熟遇到题往里面套效率反而高很多。这套骨架的核心思想很简单右指针永远向前左指针只负责“在必要时追赶”。通用伪代码大致是这个样子初始化 left 0, 窗口状态 state 初始值, 结果 res for right in 0..n-1: 把 nums[right] 纳入 state 如果窗口满足合法条件 尝试用当前窗口更新 res while (窗口在合法前提下还能缩小 或 需要恢复状态) 把 nums[left] 移出 state left 1 如果条件仍合法继续更新 res 返回 res位置1是“纳入右指针元素”位置2是“更新答案”位置3是“移出左指针元素”。三个位置各自承担不同角色背熟之后做题时只需要关注状态量怎么维护。2.2 三种语言落地写法对比不过同一个模板在不同语言里写起来差异不小。这里给大家我调试过的JavaScript、Python、Java三个版本都用最经典的“长度不小于target的最短子数组”来做演示这道题网上一般叫LeetCode 209。JavaScript版本也是很多人说的JS模板var minSubArrayLen function(target, nums) { let left 0; let sum 0; let res Infinity; for (let right 0; right nums.length; right) { sum nums[right]; while (sum target) { res Math.min(res, right - left 1); sum - nums[left]; left; } } return res Infinity ? 0 : res; };Python版本def minSubArrayLen(target, nums): left 0 cur_sum 0 res float(inf) for right in range(len(nums)): cur_sum nums[right] while cur_sum target: res min(res, right - left 1) cur_sum - nums[left] left 1 return 0 if res float(inf) else resJava版本public int minSubArrayLen(int target, int[] nums) { int left 0; int curSum 0; int res Integer.MAX_VALUE; for (int right 0; right nums.length; right) { curSum nums[right]; while (curSum target) { res Math.min(res, right - left 1); curSum - nums[left]; left; } } return res Integer.MAX_VALUE ? 0 : res; }注意这个模板用的是for循环驱动右指针while循环驱动左指针。右边的移动是“一步一步走”左边的移动是“压缩到不满足条件为止”两者的节奏完全是两回事。2.3 模板里最容易写错的三个地方第一答案更新的时机。上面例子里答案更新写在while循环内部也就是“满足条件时尽量缩”。如果只在大循环末尾更新一次可能会漏掉一些更优的短窗口。第二窗口状态的回退顺序。必须是先扣掉nums[left]的值再执行left反过来的话索引就错了。第三while和if的选择。左指针要不断压缩必须用while用if只压缩一次结果肯定错。这几个错误我在集训前三天反复踩后来索性在笔记里贴了一句提醒“先移出状态再移动指针最后去更新答案”当然具体顺序还要看题型比如求最大值时答案通常是在右指针移动、且完成过期清理之后更新的细节我在下一节展开。3. 三个必刷题型最大值、最小值、中位数3.1 滑动窗口最大值双端队列才是正解求固定窗口内的最大值时如果每个窗口都扫描一遍复杂度是O(n*k)肯定没法用。正解是用单调双端队列。核心思路是队列里保存元素索引且从队头到队尾对应的元素值严格递减。每次加入新元素时从队尾弹出所有比它小的旧元素因为它们已经不可能再成为后续窗口的最大值然后把队头中已经滑出窗口的索引弹掉此时队头就是当前窗口最大值。LeetCode 239是一道经典题我用JS写过一个版本var maxSlidingWindow function(nums, k) { const q []; const res []; for (let i 0; i nums.length; i) { // 移除窗口外的索引 while (q.length q[0] i - k) { q.shift(); } // 维护单调递减 while (q.length nums[q[q.length - 1]] nums[i]) { q.pop(); } q.push(i); if (i k - 1) { res.push(nums[q[0]]); } } return res; };这里有个容易被忽略的点两个while顺序不能乱。先清理过期索引再插入新元素这样能保证队头的元素一定还在当前窗口内。如果先插入再清理可能会出现队头索引已经过期、新元素又被它压制的情况结果自然出错。为什么数组最坏情况复杂度是O(n)因为每个索引最多入队一次、出队一次总操作数不超过2n。3.2 滑动窗口最小值逻辑完全对称最小值就是最大值的镜像处理。维护一个从队头到队尾递增的队列每次加入新元素时从队尾弹出所有比它大的旧元素。换句话说队头始终是当前窗口最小值。理解了最大值最小值基本不需要额外记忆。如果非得总结那就是两句话求最大值队列单调递减pop掉小的求最小值队列单调递增pop掉大的。实际做题时我最常用JSDouble ended队列模拟数组配合shift/pop思路直接在代码里。等到数据量变大shift可能变慢再用头尾双指针自己维护。不过竞赛或面试场景JavaScript数组就够了。3.3 滑动窗口中位数双堆与延迟删除的配合这是滑动窗口里最容易让人头疼的变体因为极值有单调队列这种O(n)解法中位数却没有类似线性结构可以轻松拿到。常见的解法有两种。第一种思路比较直接在每次窗口移动后把窗口内k个元素拷贝出来排序取中位数。复杂度O(n*k log k)数据量小还能用工程上不推荐。第二种是双堆法用一个大顶堆存窗口较小的一半一个小顶堆存较大的一半中位数就是堆顶之一或者两者平均。LeetCode 480滑动窗口中位数就是这种题。JS里没有内置堆通常手写或用数组模拟所以我只讲核心思路。关键点有三个插入新元素时和左堆堆顶比较大小决定进入哪个堆为了平衡两边数量可能需要把一边堆顶搬到另一边删除滑出窗口的元素时直接删除会破坏堆结构采用“延迟删除”先记下该元素待删除次数等到它出现在堆顶时再真正pop。双堆法单次操作复杂度O(log k)总复杂度O(n log k)比每窗口排序快很多。但实现细节非常多尤其是延迟删除的计数问题写错一个地方就变成双堆排序器而且越调越乱。我的建议是中位数这种题第一次写不要追求一次通过先把版本写出来再用对数器对比暴力解很快能找到逻辑漏洞。3.4 从算法题到工程滑动窗口滤波模型搜资料的时候经常会看到“滑动窗口滤波模型”“滑动窗口滤波verilog”这些词。它们本质上和算法题目里维护一个固定窗口的思路一脉相承用一个固定宽度的窗口采集数据然后对窗口内的统计量进行处理再计算输出。均值滤波就是窗口内求和取平均中值滤波就是窗口内排序取中值区别只是把数组变成了数据流把窗口变成了缓存区。对于嵌入式或FPGA场景滑动窗口滤波器还有一个特点输入与输出之间存在固定的延迟因为必须等窗口内的样本凑齐才能给出有效结果。这个延迟在算法层面就被决定好了硬件实现只是把它具体化。如果看过信号处理相关代码会发现不少实现也用到环形缓冲区和双端队列和滑动窗口题目的底层数据结构是同一套。所以别觉得刷题只对面试有用。窗口思想在监控告警、限流、网关统计、金融指标计算里都是一个常用范式把窗口内的聚合值算准背后就是这套算法能力。4. 可变窗口与字符串类题目的实战技巧4.1 什么时候用可变窗口判断一道题是否用可变窗口先看题目里有没有“连续”和“最短/最长/包含某种条件”这两个信号。有的话大概率就是可变窗口。比如“找到包含所有元音的最长连续子串”“满足字符频次的子串数量”这类题窗口大小不固定需要动态调整左右边界。可变的本质是右指针不断扩张窗口直到窗口满足了题目条件然后左指针尽可能收缩窗口寻找更优结果或统计当前合法的窗口数量。这类题最典型的特征是左窗口移动的时机和右指针移动的时机不完全同步。4.2 用哈希表维护字符频次当题目从数组换成字符串时窗口状态就不只是sum了更多是字符频次。经典题型是“最小覆盖子串”LeetCode 76要求在s里找最短子串使得子串包含t中的所有字符。这类题的状态维护一般是频次哈希表加上一个计数器。计数器代表“当前窗口中有多少个字符已经满足了频次要求”。每次右指针纳入一个新字符时如果新字符在窗口里的数量正好等于t里要求的数量计数器加1左指针移出字符时如果原本的数量恰好等于要求数量计数器减1。只有当计数器等于t的不重复字符数时窗口才是合法的。这道题和209题有个明显区别209只需要判断一个sum改动简单字符串题的状态是两个维度耦合在一起窗口收缩时频次变化一定要仔细处理。我还记得我第一次写这道题时在移出字符后更新计数器时少了一个“恰好等于”的判断结果每次收缩时计数器都乱跳整个窗口合法状态彻底失效。4.3 可变窗口的调试技巧与测试用例设计可变窗口题目的坑比较隐蔽我建议用一组测试用例练手第一个是全部字符都满足条件的极限输入第二个是完全不可能满足条件的输入第三个是窗口长度为1的输入第四个是重复字符极多的长串。这四个用例几乎能覆盖90%的边界问题。另外遇到字符串题目时可以用暴力解法做一个小型对数器来验证结果是否一致。比如字符串长度不超过10时两个解法同时跑逐条对比。对数器写起来也就二十行但能帮你把错误抽象成数据而不是靠肉眼瞎猜。5. 常见错误与排查实录我集训时踩过的坑5.1 边界定义混乱闭区间和开区间不要混着用写滑动窗口最怕左右边界一会儿闭区间、一会儿开区间。比如r代表窗口最后一个元素时窗口长度是r-left1如果你在下一个循环里把r当作“下一个待加入的位置”长度公式又变成了r-left。混用一次就会出现差一错误。我的习惯是统一使用左闭右闭区间即[left, right]都包含并且在代码注释里写明“r指向最后一格”。这样所有的长度计算都是right-left1状态判断也更统一。有的题解喜欢用左闭右开它也没有错但你必须始终坚持一种不要两种穿插着来。5.2 更新答案的位置不正确这类问题出得最多。固定窗口题答案更新时机大多数在ik-1之后也就是窗口已经形成时可变窗口题答案更新往往在左指针收缩循环里因为收缩意味着找到了一个更优的合法状态。如果更新放在外层循环末尾容易漏掉收缩时出现的最优解。实际操作中我建议在写主循环前先用注释标出三个位置右指针移动、状态更新、答案更新然后逐个填逻辑。这个方法看起来简单但能帮我减少很多“调半天发现少算一次”的无效时间。5.3 状态恢复不完整导致错误窗口收缩时需要把left指向元素从状态里完全移除。如果状态是求和直接减掉数值如果状态是频次哈希表要修改对应字符计数如果状态是双端队列要同时考虑索引过期和队尾单调性清理。这几个“状态”互相独立但是交错运行少一步就会导致下一次判断条件错误。有一道典型题是“字符串排列判断”类题目要求判断短串的某个排列是否是长串的子串我用固定窗口维护字符频次起初只在右指针进入时更新频次忘了在左指针收缩时回退结果窗口内频次越积越多永远无法匹配。后来我加了一步调试打印每次循环结束输出当前频次表对比窗口内容才发现移出字符时频次没有同步更新。5.4 推荐排查流程我集训时总结了一套排查流程分享出来给大家参考选择一个小规模测试用例手算出每一步的窗口内容在代码中打印right、left、当前窗口状态、当前答案观察是否一致如果状态不一致重点检查左指针回退和答案更新顺序如果结果不一致但状态一致重点检查答案更新条件是否错误。这套流程我基本每次调试都用。说实话滑动窗口的题并不要求多高的数学天赋它更考验的是耐心和状态敏感度。多调几次形成固定的排查路径后面刷题速度会明显提升。我个人在集训第16天的最大体会是滑动窗口不是单独一个算法它是“在连续区间上做统计维护”的一种通用思维。从数组求和到字符串覆盖从单调队列到双堆中位数核心都要回答三个问题——窗口何时扩张、何时收缩、答案何时更新。把这三个问题想清楚这套题就能串起来了。如果你刚开始刷这一块建议先把固定窗口和可变窗口的模板写熟再练最大值、中位数这两道进阶题最后回头补一轮常见错误基本就能把这类题吃透。