从昨天写完变长窗口的最后一题后我就想着今天该给这个系列结个尾了。不少同学后台私信我说滑动窗口练了几天模板背下来了但一换题目还是不会套尤其是一遇到“窗口内最大值”“左边界什么时候收”就懵。这其实是绝大多数初学者的通病。今天这篇我打算把这四天学到的滑动窗口知识彻底拉通一遍不讲没用的概念只讲三个东西滑动窗口在做什么、代码模板怎么用、以及我这两天踩坑踩出来的边界经验。不管你是零基础还是刷了五十题但感觉不透彻的大一新生看完这篇应该都能把滑动窗口这块拼图补完整。1. 为什么说滑动窗口是“剪过枝”的暴力枚举1.1 暴力枚举为什么能解但很亏先说我第一天的真实状态。拿到“长度为k的子数组的最大平均值”这种题我的第一反应就是暴力从每个下标i开始数k个数算平均值再和最大值比较。逻辑完全正确但一分析复杂度就露馅了。长度为n的数组每个起点i都要扫描k个元素总时间复杂度是O(n*k)。如果n是10万、k也是1万这题基本就跑不出来了。暴力枚举不是蠢它是最保底的思路。关键是我们要看到它到底浪费在哪——相邻的两个窗口其实有k-1个元素是重叠的。第一个窗口是nums[0]到nums[k-1]第二个窗口是nums[1]到nums[k]中间nums[1]到nums[k-1]这些元素被重复加了一遍。窗口每滑动一格真正变化的只有两个位置左边出去一个右边进来一个。反复重算那k-1个没变的数就是暴力的浪费点。1.2 剪枝思想砍掉重复劳动就是滑动窗口“剪枝算法”这个词听着很高深说白了就是一句话把暴力过程中肯定不用算、或者刚才已经算过的东西砍掉。滑动窗口就是双指针方向上一颗非常标准的剪枝树——它不去重新计算重叠区间而是维护一个“正在使用的窗口”每次只处理出窗和入窗的两个元素。还是拿最大均值举例。第一次进窗口老老实实算sum(nums[0:k])这个没法避免。之后每次滑动做一次减法再加一次加法就得到新窗口的和时间开销O(1)。这就是把O(n*k)剪枝成了O(n)。我用一个矿泉水瓶的例子记这个概念瓶子里装了k个球要算每k个球的总重量你不会每次把球全倒出来重新称只会拿走滚出去的那个、补进滚进来的那个然后更新一下总数。滑动窗口就是这个瓶子。1.3 什么时候该想到滑动窗口经过四天刷题我总结出适用滑动窗口的三个特征遇到题直接对号入座对象是连续子数组或连续子串不是乱序子序列问题里要求的是“满足某种条件的连续区间”比如长度固定、和大于目标值、无重复字符区间两端能通过移动左边界和右边界来调整而不是需要随机跳跃访问。如果这三点同时满足滑动窗口大概率就是出题人留给你的路子。如果题目要的是子序列而不是子数组或者要返回所有可能的组合那思路就应该转向动态规划或回溯别再硬套窗口了。2. 定长窗口一套模板解决一大类求和/求均值题2.1 从“第一扇窗口”开始初始化细节定生死定长窗口是滑动窗口里最温柔的一种因为窗口大小k固定不动左边界和右边界一起平移即可。先看代码再解释def findMaxAverage(nums, k): # 先把第一个窗口塞满 window_sum sum(nums[:k]) max_sum window_sum # 右边界从k开始每次滑一格 for right in range(k, len(nums)): left right - k window_sum window_sum - nums[left] nums[right] max_sum max(max_sum, window_sum) return max_sum / k代码很短但有几个细节值得琢磨。第一初始化时必须先算好第一个窗口的和然后在循环里滑动更新不能在循环里从零开始累积否则第一个窗口会被重复计算。第二left不是用另一个指针维护的而是通过right - k算出来的因为窗口长度固定左边界完全由右边界决定——这是定长窗口最省心的地方。很多新手会额外写一个left变量然后两个指针往右同步加1结果容易在边界上出错。2.2 一个窗口一个窗口推导为什么整体是O(n)我们模拟一下上面的代码跑nums [1,12,-5,-6,50,3]k 4。第一个窗口是[1,12,-5,-6]sum等于2最大和是2。right走到4left 0窗口变成[12,-5,-6,50]sum 2 - 1 50 51更新最大和。right走到5left 1窗口变成[-5,-6,50,3]sum 51 - 12 3 42最大和保持51。整个过程每个元素只被加进来一次、减出去一次每个元素经历两次操作总时间复杂度2n也就是O(n)。对比暴力枚举的O(n*k)数据量一大差距就是几何级的。写到这里给大家划个重点判断你是不是真的理解了定长窗口就看你能否立刻说出每次循环里第一个窗口和最后一个窗口是怎么处理的。2.3 定长窗口和前缀和工具不能乱用刷题的时候经常能看到有人拿前缀和去解类似的题这里我必须把两者掰扯清楚。前缀和适合回答“任意区间[l, r]的和是多少”这种静态查询问题预处理O(n)、每次查询O(1)但不强调窗口的移动过程滑动窗口适合“在移动过程中维护一个动态状态”这种场景。定长窗口最大均值这种题前者也能做但代码会更绕一点。真正让滑动窗口无可替代的是变长窗口——左边界的移动依赖当前窗口的状态前缀和这种静态工具根本没法表达“状态是否满足条件”。所以判断标准很简单如果左边界会因为条件而改变位置就用滑动窗口如果只是单纯随机查几个区间前缀和更舒服。3. 变长窗口的关键右侧扩张左侧收缩何时收手3.1 经典题无重复字符的最长子串定长窗口理解了之后变长窗口才是真正考验逻辑的地方。拿我练过的最经典的变长题说事给定一个字符串s找出其中不含重复字符的最长子串长度。一开始我傻乎乎用暴力把每个i作为起点往后扩判断子串是否有重复复杂度O(n²)。后来才意识到这就是标准的变长滑动窗口def lengthOfLongestSubstring(s: str) - int: from collections import defaultdict window defaultdict(int) # 记录窗口内每个字符出现的次数 left 0 ans 0 for right, ch in enumerate(s): window[ch] 1 # 右边界进窗口 while window[ch] 1: # 出现重复收缩左边界直到恢复合法 window[s[left]] - 1 left 1 ans max(ans, right - left 1) return ans核心思想总结成一句话右指针负责扩张左指针负责在状态不合法时收缩窗口始终是当前右边界下最长的合法子串。右指针每走一步我们都先把新字符放进来然后检查窗口是否还合法。不合法就不断从左边踢字符直到合法为止。这里的“合法”指的是窗口内没有重复字符。3.2 左边界判断用while还是if决定成败的一行这个坑我印象极其深刻。上面代码第6行如果我把while写成if会直接挂掉。原因是窗口里可能同时存在多个重复字符或者一个字符重复了两次以上。比如字符串“abcb”当right走到b时窗口状态是“abc b”b出现了两次if只移除一个s[left]即a窗口变成“bcb”但b还是重复的答案就错了。while则会把窗口从左边一直压缩直到b只剩一个最终窗口是“cb”。初学者最容易在这犯迷糊。我后来总结了个口诀只要收缩动作可能执行多次就必须用while能确定最多执行一次才用if。老老实实全用while最多就是多循环几次不会错。3.3 变长窗口的通用框架刷完“长度最小的子数组”“无重复字符的最长子串”“最小覆盖子串”这些题后我把变长窗口总结成一个可复现的框架初始化left 0创建一个用于记录窗口状态的数据结构哈希表、计数数组、变量等用for循环让right从0遍历到末尾每次把nums/right指向的元素纳入窗口状态判断当前窗口是否不满足题目条件比如有重复、和太大、种类太多不满足就while收缩左边界同步更新状态收缩结束后窗口是当前right下满足条件的最优窗口用窗口长度/和/最大值去更新答案。这个框架能覆盖大部分变长窗口题。难点在于第三步“判断不满足条件”的逻辑怎么写——这个不满足条件一定得是“随左边界收缩能恢复”的条件而不是像“窗口所有元素之和等于target”这种并非单调的条件。一碰到后者滑动窗口就不适用了得考虑哈希表加前缀和。4. 窗口最值用单调队列把堆和暴力都比下去4.1 先看暴力再看堆死因各不相同“滑动窗口最大值”这题我卡了老半天。给定数组nums和一个滑动窗口k要求返回每个窗口里最大的元素。我第一反应是两个方案。方案一是暴力对每个窗口扫一遍找最大值时间复杂度O((n-k1)k)也就是O(nk)跟定长窗口暴力一样数据一大就没了。方案二用堆维护一个大顶堆堆顶是最大值每次窗口滑动就把出窗元素标记为延迟删除入窗元素直接进堆取答案时把堆顶已经不在窗口中的元素弹掉。这个方法能把复杂度降到O(n log k)已经算能用了但代码写起来琐碎——既要维护下标、又要做延迟删除还得手动清理堆顶。让我比较意外的是这个题其实有更优、也更符合滑动窗口气质的解法单调队列。它把时间复杂度压到令人舒服的O(n)。我知道有些同学第一反应是“堆都O(n log k)了还不够快吗”刷题平台上确实能过但作为学算法的人我觉得还是得搞明白O(n)的做法是怎么回事毕竟“滑动窗口最小值/最大值”是一整套套路掌握了模板以后遇到同类题就是默写级别。4.2 双端队列里存下标不存值单调队列的思路是这样的维护一个双端队列deque队列里的元素按“窗口内下标递增值单调递减”的方式存储。每次新元素入队之前先把队尾所有“比新元素小或等于新元素”的值全部弹出因为这些值在新元素存在期间永远不可能成为窗口最大值了——新元素更新、更大、且在窗口里存活更久。然后再把新元素下标入队。接着检查队头下标是否已经滑出窗口滑出就弹出。最后当窗口形成后队头对应的值就是当前窗口最大值。写成代码就是下面这样from collections import deque def maxSlidingWindow(nums, k): q deque() # 队列里存下标不是值 res [] for i, v in enumerate(nums): while q and nums[q[-1]] v: q.pop() # 队尾那些会被v压制的下标全部踢掉 q.append(i) # 新元素下标入队 if q[0] i - k: # 队头已经不在当前窗口里 q.popleft() if i k - 1: # 窗口满了开始记录答案 res.append(nums[q[0]]) return res为什么队列里存下标而不是存值因为只有下标才能判断元素是否滑出窗口。判断条件是q[0] i - k如果队头下标不在窗口区间[i-k1, i]内就说明它已经过期。如果只存值你根本不知道它在窗口里的位置也就没法处理过期问题。这个点是单调队列最容易栽的地方我在第三天调试时就是因为存值结果调了半天换成下标之后一下就通了。4.3 单调队列为什么比堆更契合滑动窗口打个比方堆就像一株需要你定期修剪的老树每次滑动都要检查树顶那颗果子是否还属于现在的窗口不属于就得砍掉再重新看单调队列则像一条随时自动清理的传送带大元素进来时把所有不可能再出头的小元素直接丢下车剩下的永远是有资格竞争的选手。为什么能这么干因为窗口滑动是有顺序的元素过期也是按顺序的——新元素总是比旧元素晚过期。所以用一个队列就能同时维护“数值的优先性”和“位置的顺序性”。堆的问题在于它只维护了“数值优先”这一维度“位置过期”只能靠额外判断补救复杂度自然就上去了。5. 滑动窗口里的高频翻车点和我的调试技巧5.1 翻车点一窗口第一次记录答案的时机定长窗口题里经常有人把答案更新放在滑动循环之前或者放在窗口还没满的时候结果少记了窗口或者记录了错误区间。我在练习时总结了两种时机分别对应两类题定长窗口一般是先初始化第一个窗口并记录再从k开始滑动变长窗口一般是窗口满足条件之后在收缩结束、右指针固定时记录。判断时机的标准只有一个记录答案时窗口必须是“当前条件下的有效窗口”。既不能小于要求也不能包含非法元素。写代码之前先在纸上把第0步、第1步模拟一遍比写完再调试省太多时间。5.2 翻车点二数组下标越界的隐秘形式变长窗口最容易碰到的越界不是left 0或right n这种一眼可见的而是状态数组访问越界。比如处理字符相关的题时用长度为26的计数数组char - a下标如果字符串里混进了大写字母或者其他符号瞬间就会数组越界。我吃过的亏是用字典记录字符出现次数时忘记检查key是否存在就做加减Python里会报KeyError或产生错误计数。好习惯是涉及字符统计就用长度为128的ASCII数组或者用defaultdict别手动判断。5.3 我强烈推荐的手绘调试法调试滑动窗口的题我实验过多打日志、断点单步效率最高的反而是最原始的方法——手写模拟表。拿“长度为k的子数组最大和”举例我会画一张表左边列写right中间列写窗口区间[left, right]右边列写执行的操作入窗、出窗、更新答案。每次只画5个数据点确保循环每走一步窗口的状态都和代码输出一致。一旦发现某一步状态对不上问题基本就锁定在那一步的代码里了。这个方法笨但治根。我认识不少刷了上百题的老手遇到卡壳时也照样回到纸面上推演。5.4 滑动窗口、双指针、单调栈别再搞混刷了几天算法之后我发现这三个东西经常被放在一起比较。严格来说滑动窗口是双指针的一种应用重点在于维护一个连续的区间双指针更泛化覆盖有序数组的相向/同向移动单调栈则用于找“下一个更大/更小元素”这种两侧最近关系的题。我给自己的区分标准是如果需要维护连续区间里的某种统计性质就用滑动窗口需要找左右两边最近的更大/更小值用单调栈需要比较两个序列或在有序数组里找二元组用双指针。三者不是互相替代的关系而是针对不同需求的不同工具。6. 系列最后一天留给自己和新人的刷题建议6.1 我的分阶段题单照着刷不迷路这四天我给自己排了一条循序渐进的刷题路线今天正好一并整理出来给同样从零开始的人参考阶段一定长窗口热身长度为k的子数组最大平均数、大小为K且平均值大于等于阈值的子数组数量阶段二变长窗口入门无重复字符的最长子串、长度最小的子数组阶段三复杂窗口统计最小覆盖子串、字符串的排列、找到字符串中所有字母异位词阶段四窗口最值与单调队列滑动窗口最大值、滑动窗口中位数、绝对差不超过限制的最长连续子数组每个阶段我给自己定的标准是不看题解能独立AC两道题才算过。这个标准看着很低执行起来就会发现比想象中难因为看题解时觉得全懂了关掉题解自己写时边界条件还是会在稀奇古怪的地方出错。6.2 最后说几句心里话这两天总有人问我“学长你写的模板能直接用吗”“刷完这些是不是就够了”。我的真实感受是模板只是拐杖理解滑动窗口的底层逻辑才是学会。如果你能自己推导出“为什么相邻窗口只有两个元素变化”“为什么左边界要用while收缩”“为什么单调队列里要存下标”那面对任何新题你都不会依赖背模板。对我自己来说第四天最大的收获不是会写几道经典题而是建立了分析框架遇到连续子数组问题先检查是否满足滑动窗口的适用条件满足就按定长/变长的流程拆解不满足就换思路。这份分析习惯比记住任何模板都有用。滑动窗口这个系列到这里就收官了下一篇开始我打算继续往前进啃一啃二分答案和单调栈这几个方向到时候再把新的踩坑记录发出来。