1. 从一道题看透滑动窗口的本质1.1 这道题到底在考什么滑动窗口的最大值这个题目第一次看到的人往往会觉得很简单——不就是每次框住 k 个数找出里面最大的那个吗暴力解法两分钟就能写出来。但真正面试的时候面试官想看的从来不是你能不能写出暴力解而是你能不能在暴力解的基础上把时间复杂度从 O(nk) 压到 O(n)。这道题的核心考点其实有三个层次。第一层是窗口的维护一个固定长度为 k 的窗口在数组上从左往右滑动每次移动会进来一个新元素出去一个旧元素。第二层是最大值的快速获取如果每次窗口移动都重新遍历一遍窗口内的 k 个元素那总复杂度就是 O(nk)当 k 接近 n 的时候直接退化成 O(n²)。第三层是无效元素的及时淘汰窗口滑过去之后那些已经不在窗口范围内的旧最大值必须被清理掉否则会干扰后续的判断。我个人的经验是这道题是单调队列这个数据结构最经典的应用场景。很多人刷题刷到这道题的时候第一次接触到单调队列这个概念会觉得有点绕。但一旦理解了它的设计思想你会发现它其实非常优雅——用一个双端队列维护一个从大到小的序列队首永远是当前窗口的最大值。1.2 为什么暴力解法不够用先说说暴力解法为什么不行。假设数组长度 n 100000窗口大小 k 50000那么每次滑动窗口都要遍历 50000 个元素找最大值总共要滑动 50001 次运算量大约是 25 亿次。这个量级在 Python 里跑基本就是分钟级别的等待面试官不可能给你这个时间。暴力解法的代码大概长这样def max_sliding_window_brute(nums, k): if not nums or k 0: return [] result [] for i in range(len(nums) - k 1): result.append(max(nums[i:ik])) return result这段代码逻辑没问题但max(nums[i:ik])每次都要遍历 k 个元素而且nums[i:ik]这个切片操作本身还会创建一个新列表额外消耗内存。实测下来当 n 100000、k 1000 的时候这段代码大概要跑 3 到 5 秒完全达不到面试要求。1.3 单调队列的核心思想单调队列的思路是这样的我们用一个双端队列Python 里的collections.deque来存储数组元素的下标而不是元素本身。队列里的下标对应的元素值从队首到队尾是单调递减的。也就是说队首对应的元素永远是当前窗口里的最大值。每次窗口向右滑动一格我们需要做两件事第一件事是淘汰队首的过期元素。如果队首的下标已经小于窗口的左边界也就是i - k 1说明这个元素已经滑出窗口了必须从队首弹出。第二件事是从队尾淘汰比新元素小的元素。新元素进来的时候如果它比队尾对应的元素大那队尾那个元素就永远不可能成为未来窗口的最大值了因为新元素比它大而且比它晚出窗口所以直接从队尾弹出。重复这个过程直到队尾元素比新元素大或者队列为空然后把新元素的下标从队尾加入。这样维护下来队列里的元素始终是单调递减的队首永远是当前窗口的最大值。注意这里存下标而不是存值是因为我们需要判断元素是否已经滑出窗口。如果只存值就没法知道这个值对应的是哪个位置也就无法判断它是否过期。2. 单调队列的完整实现与逐行拆解2.1 完整代码实现先上完整代码然后逐段拆解from collections import deque def max_sliding_window(nums, k): if not nums or k 0: return [] if k 1: return nums dq deque() # 存储下标对应元素单调递减 result [] for i in range(len(nums)): # 1. 淘汰队首过期元素 if dq and dq[0] i - k 1: dq.popleft() # 2. 从队尾淘汰比当前元素小的 while dq and nums[dq[-1]] nums[i]: dq.pop() # 3. 当前元素下标入队 dq.append(i) # 4. 窗口形成后记录最大值 if i k - 1: result.append(nums[dq[0]]) return result这段代码看起来不长但每一行都有讲究。下面我逐个部分拆开讲。2.2 边界条件的处理逻辑代码开头的两个判断很关键。if not nums or k 0处理的是空数组和非法窗口大小的情况直接返回空列表。if k 1是一个优化窗口大小为 1 的时候每个元素自己就是最大值直接返回原数组即可省去队列操作的开销。很多人会忽略k 1这个优化觉得无所谓。但在实际测试中如果 k 1 且 n 很大走完整队列流程会多出很多不必要的判断和操作。虽然复杂度还是 O(n)但常数项会大不少。这种小优化在面试里是加分项能体现你对边界情况的敏感度。还有一个容易被忽略的边界是k len(nums)。按照题目的一般定义这种情况下窗口根本无法形成应该返回空列表。上面的代码里因为i k - 1这个条件永远不会满足i 最大是 len(nums) - 1而 k - 1 len(nums)所以 result 会保持为空逻辑上是正确的。2.3 队首淘汰的时机与判断if dq and dq[0] i - k 1这一行是淘汰过期元素的关键。窗口的右边界是 i左边界是i - k 1。如果队首的下标小于左边界说明这个元素已经在窗口左边外面了必须弹出。这里有个细节为什么用if而不是while因为每次窗口只滑动一格最多只会有一个元素过期。队首的下标是单调递增的因为入队顺序就是下标递增所以每次最多弹出一个。用if就够了用while也不会错但没必要。我见过有人写成while dq and dq[0] i - k这个判断和dq[0] i - k 1是等价的但前者更容易理解——队首下标小于等于窗口左边界减一就是过期。两种写法都可以选一种自己不容易搞混的就行。2.4 队尾淘汰的循环逻辑while dq and nums[dq[-1]] nums[i]这个循环是单调队列的灵魂。它的作用是把所有比当前元素小的队尾元素全部弹出去保证队列的单调递减性质。为什么可以放心地弹出这些元素因为当前元素 nums[i] 比它们大而且下标比它们靠后意味着当前元素会比它们晚出窗口。既然当前元素又大又活得久那些小的旧元素就永远没有机会成为最大值了留着也是占位置。这里用而不是是为了处理重复元素的情况。如果窗口里有多个相同的最大值用可以保留最早进入的那个避免不必要的弹出。当然用也不会影响结果的正确性只是队列里会少留一些元素。两种写法都可以看个人习惯。实操心得这个 while 循环的均摊复杂度是 O(1)。虽然看起来可能一次弹出很多元素但每个元素最多入队一次、出队一次所以整个循环下来总的弹出次数不超过 n 次。这就是单调队列能做到 O(n) 的关键。2.5 结果收集的时机控制if i k - 1这个条件控制的是什么时候开始记录结果。当 i k - 1 的时候第一个完整的窗口才刚刚形成下标 0 到 k-1此时队首就是第一个窗口的最大值。在此之前窗口还没填满不应该记录。这个判断也可以写成if i 1 k意思是一样的。我习惯用i k - 1因为直接对应窗口右边界到达 k-1这个物理意义读起来更直观。3. 复杂度分析与性能实测3.1 时间复杂度为什么是 O(n)单调队列解法的时间复杂度是 O(n)这个结论很多人知道但能说清楚为什么的人不多。关键在于均摊分析。整个算法的主循环执行 n 次。每次循环里队首淘汰最多执行一次O(1)队尾淘汰的 while 循环虽然可能一次弹出多个元素但每个元素在整个算法生命周期内最多被弹出一次。也就是说n 次循环里队尾淘汰的总操作次数不超过 n 次。把这两部分加起来总操作次数是 O(n) O(n) O(n)。这种每个元素只进出一次的分析方法是均摊复杂度分析的典型套路。类似的还有单调栈、并查集的路径压缩等。理解了这个套路以后遇到类似的数据结构就能快速判断复杂度。3.2 空间复杂度的考量空间复杂度是 O(k)因为队列里最多同时存 k 个元素窗口大小。但实际上由于队尾淘汰的存在队列里的元素通常远少于 k 个。最坏情况是数组本身单调递减比如[5, 4, 3, 2, 1]这时候队列里会存满 k 个元素。结果数组 result 的长度是n - k 1这是必须的开销不算在额外空间里。如果面试官问能不能原地修改理论上可以把结果写回原数组的前n - k 1个位置但这样会破坏原数组一般不建议。3.3 暴力解与单调队列的实测对比我本地跑了一组对比测试环境是 Python 3.10普通笔记本。测试数据是随机生成的整数数组结果如下数组长度 n窗口大小 k暴力解法耗时单调队列耗时100001000.08s0.003s10000010008.2s0.03s100000010000超时60s0.35s从表格能明显看出随着数据规模增大暴力解法的耗时呈平方级增长而单调队列基本是线性增长。当 n 1000000 的时候暴力解法已经跑不动了单调队列还能在 0.35 秒内出结果。这个对比也说明了一个道理面试里如果只能写出暴力解基本等于没做。面试官出这道题就是冲着 O(n) 解法来的。4. 常见坑点与排查技巧4.1 存值还是存下标这是新手最容易踩的坑。很多人第一反应是往队列里存元素的值写出来大概是这样# 错误示范 dq deque() for i in range(len(nums)): while dq and dq[-1] nums[i]: dq.pop() dq.append(nums[i]) if i k - 1: result.append(dq[0])这段代码的问题在于它无法判断队首元素是否已经滑出窗口。比如数组是[9, 8, 7, 6, 5]k 3当窗口滑到[7, 6, 5]的时候队列里可能还留着 9但 9 早就出窗口了结果就会出错。正确的做法是存下标通过下标去访问值同时用下标判断是否过期。这个坑我当年也踩过后来养成了一个习惯凡是涉及窗口边界的队列/栈问题一律存下标。4.2 结果收集的时机搞错另一个常见错误是结果收集的时机不对。有人写成if i k这样会漏掉第一个窗口的结果。因为第一个完整窗口形成的时候i 正好等于 k - 1而不是 k。还有人写成在循环外面单独处理第一个窗口这样代码会变得很啰嗦。最简洁的写法就是在循环里用if i k - 1统一处理逻辑清晰不容易出错。4.3 队列为空的判断遗漏while dq and nums[dq[-1]] nums[i]里的dq判断不能省。如果队列为空dq[-1]会直接抛 IndexError。虽然 Python 的 deque 在为空时访问[-1]确实会报错但很多人写代码的时候会忘记加这个判断尤其是赶时间的时候。同理if dq and dq[0] i - k 1里的dq判断也不能省。虽然逻辑上队首淘汰发生在入队之前队列可能为空但加上判断更保险。4.4 常见问题速查表问题现象可能原因解决方法结果比预期少一个结果收集条件写成i k改成i k - 1结果里出现已经滑出窗口的元素队列存的是值不是下标改成存下标报 IndexError队列为空时访问了dq[0]或dq[-1]加if dq判断结果顺序错乱队尾淘汰用了导致重复元素处理异常改用或检查逻辑k 1 时结果不对没处理 k 1 的边界加if k 1: return nums空数组报错没处理空数组开头加if not nums: return []4.5 调试技巧打印中间状态这道题的逻辑有点绕光看代码不容易发现问题。我的习惯是在关键位置打印中间状态比如每次循环结束时打印当前队列和结果for i in range(len(nums)): # ... 队列操作 ... print(fi{i}, dq{list(dq)}, result{result})拿一个小例子手动跑一遍比如nums [1, 3, -1, -3, 5, 3, 6, 7]k 3把每次循环的队列状态打印出来对照着看很快就能理解队列是怎么变化的。这个方法比干瞪眼看代码有效得多。5. 从这道题延伸出的解题套路5.1 单调队列的适用场景单调队列不是只用来解这一道题的。凡是涉及滑动窗口内的最值问题基本都可以用单调队列。比如滑动窗口的最小值把单调递减改成单调递增即可滑动窗口的平均值这个用前缀和更简单限制长度的子数组最大和某些动态规划问题里的状态转移优化判断能不能用单调队列关键看两点一是问题涉及一个固定或可变长度的窗口二是需要快速获取窗口内的最值。满足这两点单调队列基本就是最优解。5.2 单调队列与优先队列的区别很多人会问用优先队列堆不行吗每次把窗口元素丢进堆里取堆顶不就行了理论上可以但有两个问题。第一堆没法直接删除已经滑出窗口的元素需要用懒删除的方式每次取堆顶的时候检查一下是否过期过期就弹出。第二堆的插入和删除都是 O(log k)总复杂度是 O(n log k)比单调队列的 O(n) 差一个量级。所以优先队列能解但不是最优。面试的时候如果面试官追问能不能做到 O(n)那就必须用单调队列了。5.3 手写单调队列的通用模板把这道题的解法抽象一下可以得到一个单调队列的通用模板from collections import deque def monotonic_queue_template(nums, k): dq deque() result [] for i in range(len(nums)): # 淘汰过期 if dq and dq[0] i - k 1: dq.popleft() # 维护单调性 while dq and nums[dq[-1]] nums[i]: dq.pop() dq.append(i) # 收集结果 if i k - 1: result.append(nums[dq[0]]) return result这个模板改一改就能解滑动窗口最小值把改成改一改就能解其他变种题。建议把这个模板背下来面试的时候直接套能省不少时间。实操心得模板虽好但不要死记硬背。理解每一步在做什么比记住代码本身重要得多。面试官如果让你解释某一行背模板的人会卡壳理解原理的人能讲得头头是道。5.4 面试中的表达技巧这道题在面试里出现频率很高怎么讲清楚解法也是一门学问。我的建议是分三步走第一步先说暴力解法点明复杂度 O(nk)说明为什么不够好。这一步能体现你有基本的解题能力。第二步引出单调队列的思想重点讲清楚为什么可以淘汰队尾元素这个核心逻辑。这一步是加分项能体现你对数据结构的理解。第三步写代码边写边解释关键行。写完之后主动分析复杂度说明为什么是 O(n)。这一步能体现你的严谨性。如果面试官追问队列里为什么存下标不存值一定要能答上来。这个问题几乎每次都会被问到。5.5 相关变种题的练习建议刷完这道题建议顺手把下面几道相关题也做了加深对单调队列的理解滑动窗口的最小值把递减改成递增队列的最大值设计一个支持取最大值的队列绝对差不超过限制的最长连续子数组单调队列 双指针和至少为 K 的最短子数组单调队列 前缀和这几道题覆盖了单调队列的主要应用场景做完之后基本就能举一反三了。我个人的经验是单调队列这类数据结构光看题解没用必须自己动手写几遍写到不用看模板就能写出来才算真正掌握。最后分享一个小技巧如果面试的时候一时想不起单调队列怎么写可以先写暴力解法保底然后跟面试官说我知道有 O(n) 的解法用单调队列让我想一下具体实现。这样既不会交白卷又能争取思考时间。面试官通常更看重你的思路而不是你能不能一次写对。