滑动窗口最大值：单调队列原理与O(n)实现详解

1. 从一道题看滑动窗口的算法本质

1.1 为什么“滑动窗口的最大值”值得反复琢磨

“滑动窗口的最大值”这道题在算法面试里出现的频率极高，不是因为它的解法有多偏门，而是因为它同时考察了三件事：对窗口数据结构的理解、对单调性的运用、以及在时间与空间之间做取舍的判断力。很多人第一次做这道题，脑子里蹦出来的就是暴力法——每个窗口扫一遍取最大值。这个思路没错，但面试官想看的显然不是这个。

我最初接触这道题的时候，也觉得暴力法挺直观的：给定数组和窗口大小 k，从左到右滑动，每滑一次就遍历窗口内的 k 个元素找最大值。时间复杂度是 O(n*k)，空间复杂度 O(1)。如果 k 很小，这个方案完全能用；但如果 k 接近 n，那就退化成 O(n²) 了。面试场景下，面试官通常会追问一句“能不能优化到 O(n)”，这时候就需要引入单调队列这个核心工具。

这道题真正有价值的地方在于：它是一类“窗口内极值查询”问题的模板。你掌握了它，就能顺带解决“窗口内的最小值”“窗口内的第 k 大”“带限制的子数组最值”等一串变体。所以我不建议只把它当成一道孤立的面试题来背，而是把它当成一个可复用的算法模式来理解。

1.2 题目到底在问什么

先把题意说清楚。给定一个整数数组nums和一个滑动窗口大小k，窗口从数组最左端开始，每次向右移动一位，返回每个窗口中的最大值组成的列表。

举个例子：nums = [1, 3, -1, -3, 5, 3, 6, 7]，k = 3。

窗口依次是：

• [1, 3, -1]，最大值 3
• [3, -1, -3]，最大值 3
• [-1, -3, 5]，最大值 5
• [-3, 5, 3]，最大值 5
• [5, 3, 6]，最大值 6
• [3, 6, 7]，最大值 7

所以输出是[3, 3, 5, 5, 6, 7]。

题目本身不复杂，但边界条件不少：k 等于 1 时每个元素都是窗口最大值；k 等于数组长度时只有一个窗口；数组为空或者 k 为 0 时需要返回空列表。这些边界在写代码时都要考虑到，否则很容易在测试用例上翻车。

1.3 三种解法的整体思路对比

在动手写代码之前，我习惯先把可能的解法在纸上列一遍，比较它们的复杂度，再决定用哪个。这道题常见的解法有三种：

暴力法不用多说，写起来最快但性能最差。大顶堆的思路是把窗口内的元素放进堆里，堆顶就是最大值，但窗口滑动时需要删除离开窗口的元素，而堆不支持高效删除任意元素，所以要用“惰性删除”——堆里存(值, 索引)，每次取堆顶时检查索引是否还在窗口内，不在就弹出。这个方案能过，但代码量比单调队列多，而且复杂度也不是最优。

单调队列是这道题的标准答案。它的核心思想是：队列里只保留有可能成为最大值的元素，并且保持从队头到队尾递减。这样队头永远是当前窗口的最大值，取最大值只需要 O(1)。每个元素最多进队一次、出队一次，所以整体是 O(n)。

我个人的建议是：面试时先说出暴力法表明你能快速给出可行解，然后主动提出单调队列的优化方案，展示你对数据结构的掌握。这种“先可行再最优”的表达节奏，比一上来就憋大招更容易让面试官跟上你的思路。

2. 单调队列的核心原理拆解

2.1 单调队列到底“单调”在哪里

单调队列这个名字听起来有点抽象，其实它的本质就是一个双端队列（deque），只不过我们人为地维护了它的单调性。具体到这道题，我们维护的是一个单调递减队列：队头元素最大，往队尾方向依次减小。

为什么递减？因为我们要快速拿到窗口最大值。如果队头是最大的，那取最大值就是 O(1) 的事。那怎么保证队头最大呢？关键在于入队时的处理：当一个新元素要入队时，如果它比队尾元素大，那就把队尾元素弹出去，直到队尾元素比它大或者队列为空，然后再把它放进去。

这个操作背后的逻辑是：如果一个新来的元素比之前的元素大，那么之前的那些小元素在未来的窗口里永远不可能成为最大值了，因为新元素比它们大，而且新元素比它们“年轻”，会更晚离开窗口。既然它们已经没有价值了，就干脆提前淘汰掉。

用一个生活化的类比：假设你在排队买限量商品，队伍里每个人手里有一个号码牌，号码越大越优先。现在来了一个号码很大的人，他会把队伍末尾那些号码比他小的人全部挤走，因为那些人既没他优先，又比他早到（更早离开）。这样队伍始终保持从前往后号码递减，队首永远是号码最大的。

2.2 队列里存值还是存索引

这是一个很容易踩坑的细节。很多人第一反应是队列里直接存元素的值，但这样会有一个问题：当窗口滑动时，你怎么知道队头元素是不是已经离开窗口了？

如果只存值，你没法判断队头元素对应的是数组里的哪个位置，也就无法判断它是否还在当前窗口内。所以正确的做法是队列里存索引，通过索引去数组里取值，同时用索引来判断元素是否过期。

具体来说，当窗口右边界移动到i时，窗口的左边界是i - k + 1。如果队头索引小于i - k + 1，说明队头元素已经滑出窗口了，需要从队头弹出。

提示：存索引而不是存值，是单调队列实现中最容易忽略的细节。我见过不少人在面试时因为这一点被追问，最后卡在这里。

2.3 时间复杂度为什么是 O(n)

很多人第一次看到单调队列，会觉得“里面还有一个 while 循环弹出元素，怎么会是 O(n) 呢？”这个疑问很合理，关键在于均摊分析。

虽然入队操作里有一个 while 循环，但每个元素最多被弹出一次。也就是说，整个算法过程中，弹出操作的总次数不超过 n 次。入队操作也是每个元素一次，总共 n 次。所以总的操作次数是 O(n) 级别的，均摊到每个元素上就是 O(1)。

这一点在面试时经常被问到，建议你提前准备好这个解释。不要只说“因为每个元素最多进出一次”，要能把均摊的逻辑讲清楚，这样才显得你是真的理解了，而不是背下来的。

3. 完整代码实现与逐行解析

3.1 单调队列版本的完整实现

下面是我平时写这道题用的模板，结构清晰，边界处理也比较完整：

from collections import deque def max_sliding_window(nums, k): if not nums or k <= 0: return [] if k == 1: return nums[:] result = [] dq = deque() # 存储索引，对应值单调递减 for i, num in enumerate(nums): # 1. 弹出队尾所有比当前元素小的 while dq and nums[dq[-1]] <= num: dq.pop() # 2. 当前元素索引入队 dq.append(i) # 3. 弹出队头过期元素 if dq[0] < i - k + 1: dq.popleft() # 4. 窗口形成后记录最大值 if i >= k - 1: result.append(nums[dq[0]]) return result

这段代码不长，但每一步都有讲究。我逐段拆开说。

3.2 边界处理与初始化

开头的两个判断是防御性编程。if not nums or k <= 0处理空数组和非法窗口大小，直接返回空列表。if k == 1是一个优化，窗口大小为 1 时每个元素自己就是最大值，直接返回原数组的副本即可，省去走队列的开销。

有人可能会问：k > len(nums)的情况要不要处理？按照题目的一般约定，k 不会大于数组长度。但如果你想让代码更健壮，可以加一句if k > len(nums): return [max(nums)]。不过面试时如果题目没明确说，我一般不加，避免画蛇添足。

3.3 入队时的弹出逻辑

while dq and nums[dq[-1]] <= num这一行是单调队列的灵魂。注意这里用的是<=而不是<。为什么？

如果用<，那么当窗口内出现重复的最大值时，队列里会保留多个相同值的索引。这本身不影响结果的正确性，但会让队列变长，而且在某些变体题目里（比如要求返回最大值的位置）可能会出问题。用<=可以保证队列里没有重复值，队列更紧凑。

不过也有一种观点认为用<更好，因为可以保留更早的索引，减少后续弹出过期元素的次数。这个其实影响不大，两种写法都能过。我个人的习惯是用<=，因为逻辑上更干净：既然新元素和旧元素一样大，旧元素更早过期，那就没必要留着了。

3.4 过期元素的清理时机

if dq[0] < i - k + 1这一行负责清理过期元素。注意这里用的是if而不是while，因为每次窗口只滑动一格，最多只会有一个元素过期。用while也不会错，但没必要。

清理的时机放在入队之后、记录结果之前，这个顺序很重要。如果放在入队之前，那么当新元素把队头挤掉时，可能会误判。放在入队之后，可以保证队列里的元素都是当前窗口内的。

3.5 结果收集的触发条件

if i >= k - 1这个条件判断的是窗口是否已经形成。当遍历到索引k-1时，第一个完整的窗口才出现。在此之前，窗口还没满，不应该记录结果。

这个条件也可以用if i + 1 >= k来表达，效果一样。我习惯用i >= k - 1，因为少一次加法运算，虽然性能差异可以忽略不计，但读起来更直观。

4. 实操中的常见问题与排查技巧

4.1 队列里存值导致的索引错乱

这是新手最容易犯的错误。如果队列里存的是值而不是索引，那么当窗口滑动时，你无法判断队头元素是否还在窗口内。有些人会用nums.index(dq[0])去反查索引，但这个方法有两个问题：一是有重复元素时会返回第一个匹配的索引，可能不是你要的那个；二是index()本身是 O(n) 的，会把整体复杂度拉高。

正确的做法从一开始就存索引，取值时用nums[dq[0]]。这个习惯要养成，不要图省事。

4.2 弹出条件的等号问题

前面提到<=和<的区别，这里再展开说一下。假设nums = [3, 3, 3]，k = 2。

用<=的流程：

• i=0，队列空，入队 [0]
• i=1，nums[0]=3 <= nums[1]=3，弹出 0，入队 [1]，窗口形成，结果 [3]
• i=2，nums[1]=3 <= nums[2]=3，弹出 1，入队 [2]，窗口形成，结果 [3, 3]

用<的流程：

• i=0，队列空，入队 [0]
• i=1，nums[0]=3 < nums[1]=3 不成立，不弹出，入队 [0, 1]，窗口形成，结果 [3]
• i=2，nums[1]=3 < nums[2]=3 不成立，不弹出，入队 [0, 1, 2]，检查队头 0 < 2-2+1=1，弹出 0，队列 [1, 2]，结果 [3, 3]

两种写法结果都对，但用<时队列里会堆积重复元素，需要额外的过期检查。所以我还是推荐用<=。

4.3 窗口大小为 1 或等于数组长度的特殊情况

k = 1时，每个元素自己就是窗口最大值，直接返回原数组即可。如果不做这个特判，走队列逻辑也能得到正确结果，但多了一层不必要的开销。

k = len(nums)时，只有一个窗口，结果就是整个数组的最大值。走队列逻辑时，注意结果只在最后一步才被记录，前面的i >= k - 1条件都不满足，所以只会输出一个值。这个逻辑是对的，不需要额外特判。

4.4 常见问题速查表

4.5 一个容易被忽略的优化点

如果数组长度很大而 k 也很大，可以考虑在遍历前先做一些预处理。比如如果k == len(nums)，直接返回[max(nums)]，省去整个队列过程。这种小优化在面试时不一定加分，但在实际工程里能省一点时间。

另外，Python 的deque是双端队列的标准实现，popleft()和pop()都是 O(1) 的。不要用 list 来模拟队列，因为 list 的pop(0)是 O(n) 的，会把整体复杂度拉高。

5. 从这道题延伸出的同类问题

5.1 滑动窗口的最小值

把单调递减队列改成单调递增队列，队头就是最小值。入队时的弹出条件从nums[dq[-1]] <= num改成nums[dq[-1]] >= num，其他逻辑完全一样。这个变体经常和最大值问题一起出现，建议两个都练熟。

5.2 滑动窗口的中位数

中位数问题比最大值复杂得多，因为中位数不是简单的极值，不能只用单调队列。通常的做法是维护两个堆（一个大顶堆一个小顶堆），或者用有序容器。这道题属于进阶变体，面试中出现频率较低，但了解一下思路有好处。

5.3 带限制的子数组最值

比如“子数组长度不超过 k 的最大和”或者“窗口内最大值和最小值的差不超过某个阈值的最长子数组”。这类问题往往需要结合单调队列和双指针，是单调队列的高阶应用。如果你能把基础的最大值问题吃透，这些变体上手会快很多。

5.4 单调队列与单调栈的区别

很多人会把单调队列和单调栈搞混。简单说：单调栈解决的是“下一个更大元素”这类问题，单调队列解决的是“窗口内极值”这类问题。栈是后进先出，队列是先进先出，这个本质区别决定了它们适用的场景不同。单调栈里元素一旦被弹出就不会再回来，单调队列里元素会随着窗口滑动而过期。理解了这个区别，就不会用错工具。

6. 我在实际练习中的几点体会

第一次做这道题的时候，我花了挺长时间才理解为什么队列里要存索引而不是存值。当时看别人的题解，代码很短，但就是绕不过弯来。后来自己动手画了几遍窗口滑动的过程，把每一步队列的状态都写出来，才真正搞明白。

我的建议是：不要只看代码，一定要手动模拟一遍。拿一个长度为 6 左右的数组，k 取 3，在纸上画出每一步队列的变化，标出哪些元素被弹出了、为什么被弹出。这个过程看起来笨，但比看十遍题解都管用。

另外一个体会是，单调队列的代码虽然短，但边界条件特别多。入队的 while 条件、过期的 if 条件、结果收集的触发条件，任何一个写错都会导致结果不对。所以写完代码后，一定要用几个极端用例测一下：全递增、全递减、全部相同、k=1、k=n。这几个用例能覆盖绝大多数边界情况。

最后说一个心态上的问题。这道题在面试中出现的频率很高，但真正能一次写对的人并不多。如果你第一次没写出来，不要觉得自己不适合做算法。我见过很多工作多年的工程师，第一次遇到这道题也要想一会儿。关键是把原理吃透，多写几遍，形成肌肉记忆。等你真正理解了单调队列的运作方式，这类问题就变成送分题了。

后续如果想把这块练得更扎实，可以去找“滑动窗口最大值”的变体题来刷，比如“窗口内最大值的最小值”“每个窗口的平均值”等等。每道题都手动模拟一遍队列状态，坚持练上十来道，基本就能做到看到题目就知道该用什么数据结构了。