滑动窗口最大值：单调队列优化从O(nk)到O(n)的经典算法

1. 这一题在LeetCode题库里的位置和价值题目名字一眼就能看出坑点LeetCoce滑动窗口最大值。如果你在搜索引擎里看到这个拼写别急着笑其实它是LeetCode 239题“Sliding Window Maximum”的常见搜索变体。我在刷题群里见过不下三个人用这个拼写提问所以这个错别字某种程度上已经成了刷题圈的一个梗。无论拼写对不对你真正要面对的问题是给定一个整数数组nums和一个大小为k的滑动窗口窗口每次向右移动一位要求返回每个窗口内k个元素的最大值。这道题在LeetCode上被标记为Hard难度同时稳稳占据热门100题的位置。为什么一道看似简单的“每个窗口里找最大值”能封Hard因为如果只会暴力解法时间复杂度是O(nk)当数组长度n和窗口大小k都很大时性能直接爆炸。LeetCode给的数据范围通常是n达到10^5甚至10^6级别k也能到n的级别O(nk)在这样规模下是跑不完的。真正想通过全部测试用例需要把复杂度压到O(n)而这就引入了单调队列这个经典的优化手段。适合来啃这道题的人群我分三类说第一类是准备面试的求职者这道题出现频率极高谷歌、字节、微软等大厂都喜欢拿它考察候选人对数据结构灵活运用的能力第二类是刷LeetCode Hot 100的选手这道题在热门题单里是“栈与队列”专题的分水岭绕不过去第三类是参加周赛的玩家周赛430附近几期里滑动窗口变体题频繁出现搞懂母题之后再看变体思路会通透很多。我个人的看法是滑动窗口最大值不只是一道题它背后代表了一类“在线维护区间最值”的思维模型。理解了单调队列的做法你在面对“定长区间最大值、最小值、绝对差”等变体时基本都能举一反三。所以这篇文章不只是讲一道题的解法而是把这个思维模型的来龙去脉掰开揉碎。2. 暴力解法不可行的底层原因先把最直观的想法摆出来每次窗口滑动一格我们把窗口内的k个数字重新扫描一遍找出最大值。窗口一共有n-k1个位置每个位置扫描k个元素总复杂度就是O(nk)。用实际数字感受一下n100000k50000O(nk)就是50亿次比较在普通环境下跑完需要几十秒甚至更久。LeetCode的判题机一般限制在1到2秒内出结果这种复杂度连边都摸不着。很多人会想能不能用堆优先队列来优化思路是维护一个大顶堆堆里放窗口内的元素堆顶就是最大值。每次窗口移动时加入新元素O(log k)弹出堆顶O(log k)这样单次操作复杂度降到O(log k)整体O(n log k)。但堆解法有一个隐性痛点堆没办法快速删除窗口左侧滑出去的元素。你只能在堆里同时存下标和新值判断当前堆顶的下标是否已经滑出窗口滑出了就惰性删除。代码写起来稍显繁琐而且堆的常数因子比较大实际跑起来并不算快。更重要的是堆解法没有利用上“窗口是先进先出”这个结构特性属于“能用但不优雅”。单调队列正是冲着这个痛点来的。它利用双端队列deque维护窗口内元素的“潜在最大值候选”把复杂度真正压到O(n)。每个元素最多入队一次、出队一次均摊下来每次操作的代价是O(1)。3. 单调队列的核心逻辑拆解3.1 为什么队列要保持单调递减先想清楚一个问题窗口在滑动时我们真正关心的是哪些元素假设当前窗口内有两个元素左边一个是5右边一个是3而且5的下标更小更早入窗口。请问窗口向右滑动的过程中3有没有可能在5离开窗口之前成为最大值答案是不可能。因为3小于5只要5还在窗口里最大值就轮不到3。只有当5被滑出窗口之后3才有机会被考虑。这个观察引出一个关键结论如果队列中存在下标更小、值也更小的元素那么它在未来永远不会成为最大值候选项应该直接丢弃。反过来如果队列中下标更小、值更大的元素它暂时是最大值但要把它保留到它滑出窗口为止。所以队列要维护的是一个单调递减的序列从队头到队尾元素的值严格递减。队头永远是当前窗口的最大值队尾是当前窗口的最小候选。3.2 双端队列的三种操作队列里的每个元素存储的是数组下标而不是元素值。为什么要存下标而不存值因为窗口滑动时我们需要判断某个元素还在不在窗口内这必须知道它的位置。存下标可以通过nums[i]随时取值还能用来判断过期一举两得。具体操作分为三步第一步入队前的“尾部清理”。新元素nums[i]入队之前先把队列尾部所有小于等于nums[i]的元素全部弹出。为什么连等于也要弹出因为如果存在两个相同的最大值下标更小的那个会先滑出窗口而下标更大的那个能活得更久。保留靠右的那个在淘汰旧元素时更安全不会影响窗口后续的最大值判断。第二步入队。把当前下标i从尾部压入队列。第三步窗口满员后的“头部过期检查”。当窗口完全成形后检查队头下标是否等于i-k如果等于说明它正好滑出了当前窗口从队头弹出。这种判断方式的精妙之处在于由于我们保证了队列严格单调递减队头只有一个元素判断是否过期只需比较下标是否等于i-k不需要用或避免误删。这三个操作的顺序非常重要必须先清理尾部再入队这样队列的单调性才能维持头部过期检查则要在窗口满员之后进行。当i小于k-1时窗口还没完全成形不需要输出最大值。我画个简单的时间轴帮助理解i从0开始遍历nums每当i到达k-1窗口内恰好有k个元素输出一次队头值。之后每移动一步先做尾部清理再做头部过期检查然后输出队头。这个顺序在代码里就是几行循环的事但逻辑闭环必须严格。3.3 手动走一遍完整过程用nums [1,3,-1,-3,5,3,6,7]k 3来手动推演。i0nums[0]1队列空1入队队列[0]窗口未满。i1nums[1]3队尾nums[0]1 3弹出03入队队列[1]窗口未满但最大值其实是3。i2nums[2]-1队尾nums[1]3 -1保留-1入队队列[1,2]。窗口已满队头下标1对应值3输出3。i3nums[3]-3队尾nums[2]-1 -3保留-3入队队列[1,2,3]。然后做头部过期检查i-k0队头是1不等于0不需要弹出输出队头值3。这个窗口[3,-1,-3]的最大值确实是3。i4nums[4]5。先清理尾部队尾下标3的值-3 5弹出队尾下标2的值-1 5弹出队尾下标1的值3 5弹出。队列空了5入队队列[4]。头部过期检查i-k1队头是4不等于1不需要弹出输出5。这个窗口[-1,-3,5]最大值是5。i5nums[5]3队尾nums[4]5 33入队队列[4,5]。头部过期检查i-k2队头是4不等于2输出5。窗口[-3,5,3]最大值5正确。i6nums[6]6。队尾下标5的值3 6弹出队尾下标4的值5 6弹出。6入队队列[6]。头部过期检查i-k3队头下标6不等于3输出6。窗口[5,3,6]最大值6正确。i7nums[7]7。队尾下标6的值6 7弹出。7入队队列[7]。头部过期检查i-k4队头下标7不等于4输出7。窗口[3,6,7]最大值7完美收官。最终输出数组为[3,3,5,5,6,7]与LeetCode样例完全一致。这个推演过程非常值得自己跟着写一遍因为单调队列的每个弹出操作在书面上看似简单真正手推时才能体会到“为什么要先清尾部、再查头部”的顺序逻辑。4. 完整代码实现与关键参数说明4.1 C实现class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { dequeint q; vectorint res; int n nums.size(); for (int i 0; i n; i) { // 1. 尾部清理维护单调递减 while (!q.empty() nums[q.back()] nums[i]) { q.pop_back(); } // 2. 入队当前下标 q.push_back(i); // 3. 窗口成形后检查队头是否滑出 if (i k) { if (q.front() i - k) { q.pop_front(); } } // 4. 窗口满后记录当前窗口最大值 if (i k - 1) { res.push_back(nums[q.front()]); } } return res; } };几个关键点展开说明尾部清理用while循环。注意这里用的是而不是我已经解释过原因相同值的元素保留靠右的能减少队头过期误判的概率。如果用队列里可能出现相等值的情况虽然不影响输出结果但会多存储一些永远不会成为最大值候选的元素空间上不划算而且处理上还会增加额外判断。头部过期检查放在i k的条件下。为什么不是i k-1因为在输出最大值之前队头有可能是这个窗口内的合法最大值但滑动窗口已经发生了位移。仔细看当ik时窗口覆盖的范围是下标1到k原本下标0的元素已经滑出所以这时候就要检查队头是不是下标0即i-k。如果用i-k-1或i-k1去判断下标就会错位后期会出现窗口内明明还有元素却把最大值弹出的bug。i k - 1这个条件负责“窗口满员”。只有当窗口内有了k个元素才能输出队头最大值。这两个条件一个负责过期清理、一个负责输出时机分工明确不要混在一起。4.2 Python实现from collections import deque class Solution: def maxSlidingWindow(self, nums: List[int], k: int) - List[int]: q deque() res [] n len(nums) for i in range(n): while q and nums[q[-1]] nums[i]: q.pop() q.append(i) if i k and q[0] i - k: q.popleft() if i k - 1: res.append(nums[q[0]]) return resPython版本和C逻辑完全一致。需要注意的是Python的deque在popleft()上是O(1)的list的pop(0)是O(n)千万别用list当作队列来写这道题否则复杂度会退化成O(n^2)。这个坑我在群里见过好几个同学踩过。4.3 复杂度对比| 方法 | 时间复杂度 | 空间复杂度 | 说明 | |------|-----------|-----------|------| | 暴力 | O(nk) | O(1) | 每窗口全量扫描n和k大时不可接受 | | 大顶堆 | O(n log k) | O(k) | 需要惰性删除常数大 | | 单调队列 | O(n) | O(k) | 每个元素至多入队出队一次 |单调队列的O(n)是均摊意义下的复杂度。每个元素进入队列一次、弹出一次总操作次数不超过2n因此总代价是O(n)。即使窗口大小为1也不会出现退化每个元素入队后立刻被下一次循环的尾部清理弹出同样保持均匀分布。5. 变体题型与周赛实战延伸5.1 周赛430那题的关联刷到LeetCode周赛430附近时会有几道题和工作原理相近但包装不同的题目。比如一类题要求返回每个滑动窗口内的最小值或者同时返回最大值和最小值。思路完全一致把单调递减队改成单调递增队即可如果需要同时维护最大值和最小值就同时开两个双端队列。还有一类变体是“窗口内最大值的个数统计”这类题会在周赛里以中等难度出现。解法是先计算出每个窗口的最大值数组再对标定的区间做统计单调队列依然是最优工具。如果没搞懂母题变体做起来会非常吃力。5.2 073爱吃香蕉的狒狒带来的启发在LeetCode热门题单里还有一道073“爱吃香蕉的狒狒”它跟滑动窗口最大值看起来毫无关联一个是二分查找、一个是单调队列但背后有共同的思想在每一步决策中想办法把数据规模降下来。滑动窗口最大值通过剔除“永远不可能是最大值”的候选元素来降低维护成本爱吃香蕉的狒狒通过二分查找来将逐小时尝试的O(maxPile)复杂度降为O(log maxPile)。这种“思考哪些元素/哪些分支可以剪掉”的思路在刷题中几乎是万能钥匙。所以我建议刷题时不要孤立地刷每一道题把这类“通过剔除不可能项来优化”的题目放在一起对比学习效率和记忆深度都会翻倍。同类型的还有“接雨水”“柱状图最大矩形”里的单调栈问题它们是单调队列的近亲。5.3 从滑动到定长区间的思维迁移如果把题目稍微改一下给定一个数组求所有长度为k的连续子数组中最大值与最小值的差的最大值。本质上就是同时维护单调递减和单调递增两个队列在窗口移动过程中同步更新两个队列的队头然后计算差值。再改一个版本给定一个数组和一个阈值求最长的连续子数组使得子数组内最大值与最小值之差不超过该阈值。这个问题是单调队列的经典应用典型如LeetCode 1438题“绝对差不超过限制的最长连续子数组”。做法是同时维护最大值队列和最小值队列窗口右端点不断扩张一旦差值超过限制左端点右移直到重新满足条件。这个变题在面试中经常作为239题的follow-up出现。如果你只背了239题的解法面试官把约束条件换成“限制差值”很可能直接懵掉。理解了“队头提供极值窗口滑动时同步调整”的核心思想后无论怎么包装都能快速拆解。6. 常见错误与实战排查记录6.1 队头过期判断的下标错位这是我最常见到的错误。很多人写成了if (q.front() i - k)或者if (q.front() i - k)从结果看好像也对但逻辑上不够精确。关键在于单调队列保证每个下标最多入队一次、出队一次队头不会有“积压多个过期元素”的情况。当窗口滑出某个元素时如果它恰好是队头那它一定是最早入队的那个元素也就是下标等于i-k的那个元素。所以用判断就够了既不会漏删除也不会误删还在窗口内的元素。但如果用了在某些边界情况下队头可能已经被提前弹出的元素“顶替”后仍存在历史下标可能导致不必要的出队但最终多几次判断仍然能保持正确性。唯一的小风险是“等号”判断在k1时的工作条件需要单独验证。k1时窗口只有一个元素每个循环都会清空队列再入队队头必然等于i-k所以代码依然正确。我测试过k1、kn、n0、k0这些边界全部通过。6.2 尾部清理时忘了用等号如果用nums[q.back()] nums[i]而不是队列中会存在相等值的多个元素。例如nums[5,5,5]k2时队头会挤着下标0和1两个值相同的元素。输出时最大值为5看起来没问题但当第一个5滑出时队头弹出的是下标0留下来的还是下标1仍然能维持窗口正确性。这不是致命错误但会造成空间浪费以及无谓的队列操作。假设窗口很大且数组中重复值很多队列长度可能膨胀到k的级别依然能过测试但性能会略差。坚持用是更优雅、更严谨的写法。6.3 用list模拟deque导致超时Python新手特别容易踩用list和pop(0)来实现队列。pop(0)是O(n)操作在n10^5级别时即便总操作量仍然是O(n)次但每次弹出都涉及整个数组的前移复杂度会退化为O(n^2)。最终的结果就是本地跑小数据没问题提交时直接TLE超时。正确做法是使用collections.deque它的popleft()是O(1)。C选手则直接用标准库的deque不要自己用vector去模拟头部弹出。6.4 边界值测试清单以下这组测试用例建议在提交前手动跑一遍nums [1], k 1 - [1] nums [1, -1], k 1 - [1, -1] nums [9, 11], k 2 - [11] nums [4, -2], k 2 - [4] nums [1, 3, 1, 2, 0, 5], k 3 - [3, 3, 2, 5] nums [-7, -8, 7, 5, 7, 1, 6, 0], k 4 - [7, 7, 7, 7, 7]特别是最后一组存在连续多个相同最大值的情况需要确保队头过期处理不会把滞留在队内的相同最大值误弹。我的经验是每组边界测试手推一遍队列的状态变化比直接提交测试要稳妥得多。7. 实战调试技巧与性能优化心得在实际调试这道题时我建议用一个辅助函数打印当前队列的状态特别是在复杂数据上跑出错时打印下标和值能快速定位问题。void printQueue(dequeint q, vectorint nums) { cout queue indices: ; for (int idx : q) cout idx ; cout | values: ; for (int idx : q) cout nums[idx] ; cout endl; }在循环的每步调用这个函数你就能清楚看到每次操作后队列的变化很快理解死循环或漏输出是哪一步出的问题。性能方面单调队列的常数已经非常小了但有两个小优化习惯值得养成。第一个是关闭C的同步缓冲区在竞赛环境里用ios::sync_with_stdio(false); cin.tie(0);能有效避免输入输出上的时间损耗第二个是提前reserve结果数组的容量res.reserve(n - k 1)避免在push_back过程中反复扩容。对于Python选手可以把核心循环用列表推导加内置函数的方式略微提速但不要强行用一行式写法会大幅牺牲可读性。作为面试代码清晰的逻辑比微小的性能提升重要得多。8. 一道母题带来的整体学习路径建议滑动窗口最大值作为Hard题真正的价值在于串起一整条知识点体系。我建议沿以下路径巩固第一步彻底掌握单调队列的入队、出队、过期检查三个动作能独立手写完整代码不需要看题解。第二步独立解决LeetCode 1438“绝对差不超过限制的最长连续子数组”体会双队列配合左右指针的滑动窗口写法。第三步做LeetCode 862“和至少为K的最短子数组”这道题需要用到前缀和数组辅助也更考验对队列单调性条件的建模能力。第四步周赛遇到滑动窗口相关变题时先在草稿纸上画出队列状态再写代码。这套路径走下来面试中无论题目如何包装你都能快速识别出“这是单调队列的题”。同类母题还包括“接雨水”“柱状图最大矩形”这些单调栈问题它们与单调队列共享“维护单调性、剔除无用候选”的思想建议放在一起学。我自己的体会是这道题的难点其实不在代码本身而在于“什么时候用单调队列”的判断。如果刷题时能总结出条件当你需要在一个动态变化的区间内维护最值而且区间端点单方向移动时单调队列几乎是标准的答案模板。这个总结比记住239题的解法更有价值。最后分享一个小技巧面试时如果被问到滑动窗口最大值先写出带注释的暴力解法说明O(nk)的缺陷再引出单调队列优化。这种“先暴露问题再解决问题”的表达方式比直接甩出最优解更能体现编程素养面试官也普遍买账。