很多人第一次见到LeetCode 239“滑动窗口最大值”，第一反应是这不就是暴力扫一遍的事嘛，结果写完一提交，超时提示挂脸上，才意识到这道题没那么简单。作为热门100题里的常客，它考察的其实并不是“你会不会求最大值”，而是“你会不会维护一个动态集合的极值”——这背后是数据结构设计思想，不是单纯的编码技巧。这篇文章我会把这道题的解题思路完整拆开，从暴力解到双端队列单调方案，从原理推导到代码实现，再到面试中怎么把这道题讲出层次感，一次说透。
这道题我前前后后刷过三遍，每次重做都有新收获。第一次只会暴力，第二次学会了单调队列但写不对边界，第三次才真正理解为什么存索引而不仅仅是存值。如果你也正卡在这道题上，或者准备面试想把这题吃透，这篇内容应该能帮你省下不少弯路。
1. 先把题目“吃透”：滑动窗口最大值的题眼在哪
1.1 题目描述背后的真实诉求
先看题面：给定一个整数数组nums，有一个大小为k的滑动窗口从数组最左侧移动到最右侧，你只能看到窗口中的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, 3, 5, 5, 6, 7]
题目本身并不难理解，难点在于数据规模。题目的约束条件里，nums.length最大可以到 10 的 5 次方，k的取值也很大。如果窗口每次移动都重新扫描一遍窗口里的k个元素，总复杂度就是 O(n×k)，当k接近 50000 时，计算量是亿级别的，超时几乎是必然的。
所以这道题的“题眼”在于：随着窗口滑动，相邻两个窗口之间有 k-1 个元素是重叠的，这些重叠元素的比较结果是完全可以复用的。暴力解法的问题不是它错了，而是它每次都把已经比过的元素又重新比了一遍，做了大量的无效劳动。理解了这一点，优化方向就清楚了——怎么把重复的比较次数省掉，让总体代价降下来。
1.2 暴力解法为什么不行，瓶颈到底在哪
先写出最自然的暴力思路，也方便对比后面的优化方案：
def maxSlidingWindow(nums, k): n = len(nums) res = [] for i in range(n - k + 1): res.append(max(nums[i : i + k])) return res这段代码思路完全正确，max()内部就是一次 O(k) 的扫描。外层循环 n-k+1 次，总复杂度 O(n×k)。当 n 很大、k 也很大时，比如 n = 10^5、k = 5×10^4，计算次数大约是 5×10^9 量级，现代计算机一秒能跑 10^8 到 10^9 次简单运算，这种规模基本就卡死了。
暴力解法慢的本质是什么？举个例子：窗口从[1, 3, -1]滑到[3, -1, -3]，重叠部分是[3, -1]。理论上，第一个窗口已经比较过 3 和 -1 的大小关系，第二个窗口可以直接复用这个结论——因为 3 比 -1 大，对这两个元素的相对顺序而言，新的最大值候选依然是 3（如果它没过期的话）。但暴力解法完全不记这个信息，每次都把窗口里所有元素重新比一遍，相当于每次移动都重算了一遍重叠部分的比较结果。
这就像你在排队打饭，每次队伍往里走一个人，你就要从头到尾把所有排队的人重新数一遍身高找最高的——其实大部分人的身高你上次已经看过了。真正需要关注的，只有新来的人有多高、队首的人有没有离开。
2. 从 O(n×k) 到 O(n)：单调队列为什么是标准答案
2.1 用一个“候选者名单”来动态维护最大值
优化的核心思路是：维护一个始终有序的候选最大值名单，窗口滑动时只做两个动作——新增一个候选项，移除一个过期项。这个名单有这样一个性质：排在越前面的元素，值越大，而且“存活时间”也越久。
具体来说，名单里保存的是数组元素的下标（索引），而不是元素值本身。为什么要存索引而不是存值？因为光是知道“最大的数是 3”没用，你没法判断这个 3 是不是已经滑出了窗口。而存了索引之后，窗口的左边界是已知的，只要索引小于左边界，就说明这个值已经过期，直接移除。
比如窗口左边界是 2，当前候选名单的队头索引是 1，那就说明这个索引对应的元素已经在窗口左边外了，过期了，弹出。如果队头索引是 3，还在窗口内，那它依然是当前窗口的最大值候选。
这个数据结构就是单调递减队列：从队头到队尾，元素对应的值依次递减。队头永远是当前窗口的最大值——因为只有最大的才有资格站队头，其他的都在它后面“候补”。
2.2 入队时为什么要从尾部“顶掉”小的
这是单调队列最核心的一个操作，也是很多人第一次看代码时最容易困惑的地方。先看规则：每次新元素入队前，把队尾所有值小于等于它的元素全部弹出。然后新元素从尾部入队。
为什么要把队尾小的全部弹出？因为窗口向右滑动，新元素的“出生时间”一定晚于队列里任何已有的元素。对于任何一个已有的、值比新元素小的元素，在新元素存活期间，它永远不可能成为窗口最大值——新元素比它大，且比它晚过期。所以它留在队列里没有任何意义，只会白白增加队列的长度和比较次数。
举例来说，队列里现在存的索引对应的值是[7, 5]，新来的元素值是 6。5 会被弹出，7 保留。为什么 5 要被弹出？因为 7 还在队列里，最大值至少是 7；就算以后 7 过期了，还有 6 在，5 依然排不上号。所以 5 是一个永远出不了头的“备胎”，留着没用。
这里有个细节很多人会写错：弹出条件是“小于等于”而不是“小于”。为什么相等时也要弹出？举个例子，队列里有个值是 5，新来的值也是 5。如果只弹出小于的，那么队列里就会有连续两个 5。这两个 5 谁更适合当候选？新来的 5 索引更大、过期更晚，旧 5 能活的窗口，新 5 都能活，而且新 5 的值不比旧 5 小。所以旧 5 直接淘汰，让新 5 顶替上去。这个细节在写代码时非常容易漏。
2.3 窗口移动时的“过期弹出”和“结果记录”时机
入队淘汰讲清楚了，再看窗口移动的完整流程。假设窗口大小是 k，遍历数组到位置 i 时，流程分三步：
第一步，执行入队前的淘汰：把队尾所有值小于等于nums[i]的索引全部弹出。这保证了队列单调递减。
第二步，把索引 i 从队尾入队。
第三步，检查队头索引是否过期：如果队头索引小于等于i - k，说明它已经不在当前窗口内了，弹出。
第四步，如果窗口已经形成（即 i 大于等于 k-1），把队头索引对应的值加入结果数组。
为什么要先淘汰再入队，而不是先入队再淘汰？其实这两种写法都能实现，但先淘汰再入队逻辑更清晰：你先让队列保持单调递减的性质，新元素进来之后队列依然有序；如果先入队再淘汰，新元素可能在队尾，也可能在中间，处理起来反而更容易乱。
结果记录的时机也要注意：窗口还没完全形成时，队列里虽然已经维护了一部分元素，但长度不够 k，这时候记录最大值是没有意义的。所以要从 i = k-1 开始才记录，也就是第一个完整窗口的最后一个元素进入队列之后。
我一开始写的时候，容易把过期检查放在入队淘汰的前面，这样也没错，但要注意顺序别写反。更稳妥的写法是：先淘汰队尾小数 → 入队 → 再淘汰队头过期 → 记录结果。四个步骤一次到位。
3. 两种主流写法的完整实现与对比
3.1 单调队列 + 双端队列的最终版本
单调队列需要一个“两头都能操作”的数据结构：队头要能弹出过期元素，队尾要能弹出小值再入队新值。Python 的collections.deque、Java 的ArrayDeque、C++ 的std::deque都是专门干这个的。
Python 实现如下：
from collections import deque def maxSlidingWindow(nums, k): n = len(nums) if n == 0 or k == 0: return [] # 双端队列里存的是数组下标 dq = deque() res = [] for i in range(n): # 1. 维护单调递减：队尾所有小于等于当前值的下标全部弹出 while dq and nums[dq[-1]] <= nums[i]: dq.pop() # 2. 当前下标入队 dq.append(i) # 3. 队头过期检查：超过窗口范围就弹出去 if dq[0] <= i - k: dq.popleft() # 4. 窗口形成后，记录队头对应的值 if i >= k - 1: res.append(nums[dq[0]]) return resJava 版本的核心逻辑完全一致：
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if (nums.length == 0 || k == 0) return new int[0]; int n = nums.length; int[] res = new int[n - k + 1]; Deque<Integer> dq = new ArrayDeque<>(); int idx = 0; for (int i = 0; i < n; i++) { while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) { dq.pollLast(); } dq.offerLast(i); if (dq.peekFirst() <= i - k) { dq.pollFirst(); } if (i >= k - 1) { res[idx++] = nums[dq.peekFirst()]; } } return res; } }用题目给的例子验证一遍：nums = [1, 3, -1, -3, 5, 3, 6, 7]，k = 3。
- i=0，队列空，1 入队，队列：
[0]，不满足记录条件 - i=1，nums[1]=3，队尾 1 被弹出（因为 1 <= 3），索引 1 入队，队列：
[1]，不记录 - i=2，nums[2]=-1，-1 比 3 小，直接入队，队列：
[1, 2]，窗口形成，记录nums[1]=3 - i=3，nums[3]=-3，入队，队列：
[1, 2, 3]，队头索引 1 大于 0，未过期，记录nums[1]=3 - i=4，nums[4]=5，队尾 -3、-1、3 依次弹出，索引 4 入队，队列：
[4]，记录nums[4]=5 - i=5，nums[5]=3，入队，队列：
[4, 5]，记录nums[4]=5 - i=6，nums[6]=6，队尾 3 弹出、5 弹出，索引 6 入队，队列：
[6]，记录nums[6]=6 - i=7，nums[7]=7，队尾 6 弹出，索引 7 入队，队列：
[7]，记录nums[7]=7
最终结果[3, 3, 5, 5, 6, 7]，和预期完全一致。整个过程里每个元素最多入队一次、出队一次，均摊复杂度 O(n)，空间复杂度 O(k)。
3.2 优先队列（堆）也是一种解法，但优劣要拎清
除了单调队列，这道题还有一个经典解法：用最大堆。堆里存(值, 索引)的二元组，每次窗口移动时把新元素入堆，然后检查堆顶元素的索引是否还在窗口内，如果过期就弹出，一直到堆顶元素在窗口内，它就是当前窗口的最大值。
import heapq def maxSlidingWindow(nums, k): n = len(nums) if n == 0 or k == 0: return [] # 最大堆存 (-值, 索引)，Python的heapq默认最小堆，取负变成最大堆 heap = [] res = [] for i in range(n): heapq.heappush(heap, (-nums[i], i)) # 弹出所有过期的堆顶 while heap and heap[0][1] <= i - k: heapq.heappop(heap) if i >= k - 1: res.append(-heap[0][0]) return res这个解法的复杂度是 O(n log n)，因为每次入堆、出堆都是 O(log k) 的操作。相比单调队列的 O(n)，理论上堆解法要慢一些。但堆解法的代码更短，逻辑更直接，面试时如果一时没想到单调队列，堆解法作为保底方案是完全够用的——至少不是暴力解。
不过堆解法有个隐藏问题：堆中会残留大量“已经过期的元素”，每次取最大值前需要反复弹出过期的堆顶。最坏情况下，堆的大小可能接近 n，因为过期元素没有被及时清理。虽然均摊复杂度还是 O(n log n)，但常数更大，实际运行会比单调队列慢不少。如果数组是流式输入、窗口极大，堆解法的性能劣势会更明显。
从工程角度，我更建议把单调队列作为首选方案。它不只是在 LeetCode 上跑得快，在你处理实时数据流、维护滑动窗口统计指标时，O(n) 的算法都是更可靠的选择。
3.3 两种方案的对比总结
| 维度 | 单调队列（双端队列） | 优先队列（最大堆） |
|---|---|---|
| 时间复杂度 | O(n)，每个元素进出队列各一次 | O(n log n)，堆操作对数级 |
| 空间复杂度 | O(k)，队列里最多 k 个有效索引 | O(n)，堆里可能残留过期元素 |
| 代码量 | 稍长，但逻辑固定 | 更短，思路直观 |
| 面试观感 | 展示数据结构和优化意识 | 合格的备选方案 |
| 适用场景 | 大规模数据、性能敏感场景 | 快速实现、小规模数据 |
面试时如果把两种方案都讲出来，就说明你既懂优化，又有务实兜底的能力，这是很加分的。但最终手写代码时，建议写单调队列版本——它才是这道题真正想考察的东西。
4. 跑题的例子之外：这些“易错点”和边界比题更难
4.1 四个最容易写错的地方
这道题提交记录里最常见的错误，我整理成了一份速查表：
| 易错点 | 错误写法 | 正确逻辑 | 原因 |
|---|---|---|---|
| 队列存值还是存索引 | 队列存nums的值 | 必须存索引 | 只有索引能判断是否过期；值相同的情况下索引能区分新旧 |
| 弹出条件写“<”还是“<=” | 用<判断队尾 | 用<=判断队尾 | 相等情况下新元素更新且更晚过期，旧元素应该被淘汰 |
| 记录结果的时机 | 从 i=0 开始记录 | 从 i=k-1 开始记录 | 窗口长度小于 k 时，队列头不一定是真正的窗口最大值 |
| 过期判断的边界 | dq[0] < i-k | dq[0] <= i-k | 窗口左边界是 i-k+1，索引等于 i-k 的元素已经不在窗口里 |
dq[0] <= i - k这个边界很多人会写错成<。举个例子，窗口大小 k=3，当前 i=5 时，窗口覆盖的索引是 3、4、5。左边界是 i-k+1 = 3。队头索引如果是 3，那么它是窗口内元素，不能弹；如果是 2，已经过期，要弹。判断条件dq[0] <= 2才能把索引为 2 的元素弹出去。如果你写成dq[0] < 2，索引 2 就永远弹不出去，结果里就会出现“窗口外的数”。
4.2 空数组、k=1、k=n 这些边界怎么处理
边界测试是刷题中特别容易翻车的环节。我每次写完都会顺手跑几个特殊用例：
nums = []：直接返回[]。代码开头如果没有判空，访问nums[0]就会报错。k = 1：窗口本身就是单元素，结果就是原数组。单调队列的逻辑不受影响，每个元素入队后立刻记录，正常返回。k = n：只有一个完整窗口，结果数组就是整个数组上长度为 n 的最大值，也就是全局最大值。这时候过期检查基本不会触发，逻辑依然正确。k > n：题目一般保证 k <= n，但如果自己测试时不小心传了k > n，结果数组长度会是负数，代码会崩。最好在开头加一行判断：if k > n: return []。
这些边界情况不复杂，但调试起来很麻烦。我的习惯是写代码时就在脑子里把 i=0、i=k-1、i=n-1 这三个特殊位置过一遍，确保逻辑自洽。
4.3 为什么不能用普通的 list 模拟队列
有些初学者会想：我用 Python 的list直接模拟队列不就行了？pop(0)弹出队头，pop()弹出队尾，看起来都能实现。
但这里有个性能陷阱：Python 的 listpop(0)是 O(n) 的操作，因为弹出第一个元素后，后面的所有元素都要往前移动一位。如果你在循环里大量执行pop(0)，总复杂度会重新退化到 O(n²)，这道题你写了单调队列的“形”，却没有得到单调队列的“神”。
deque的popleft()是真正的 O(1) 操作，因为双端队列在底层是用双向链表（或者分块数组）实现的，两头增删都不涉及整体移动。Java 的ArrayDeque同理，数组实现但用了环形结构，头尾操作都是均摊 O(1)。
这是刷题之外也很重要的工程经验：选择数据结构不是看 API 像不像，而是看操作的时间复杂度是否匹配你的算法设计。很多人背了“滑动窗口用双端队列”，但不知道为什么必须是双端队列，真正写的时候用错了容器还浑然不觉。
5. 套路迁移：这套结构能顺手解掉多少同类题
5.1 从“最大值”到“最小值”，一行改动的事
单调队列这套模板，把比较方向反过来，就是滑动窗口最小值。把nums[dq[-1]] <= nums[i]改成nums[dq[-1]] >= nums[i]，其他完全不用动。
from collections import deque def minSlidingWindow(nums, k): n = len(nums) if n == 0 or k == 0: return [] dq = deque() res = [] for i in range(n): while dq and nums[dq[-1]] >= nums[i]: dq.pop() dq.append(i) if dq[0] <= i - k: dq.popleft() if i >= k - 1: res.append(nums[dq[0]]) return resLeetCode 239 的变体题其实很多，比如求窗口内最大值的下标、求窗口中第二大的值、维护两个单调队列同时求最大值和最小值。通信和股票场景中常见的“移动平均线”配合“滚动极值”，套路完全一样。掌握模板之后，遇到任何“定长窗口极值”的题目都能直接套。
5.2 更广的迁移：单调栈和单调队列是兄弟
单调队列的背后是“单调栈”思想的一种扩展。单调栈是只在一端（栈顶）维护单调性的数据结构，典型应用是 LeetCode 84（柱状图中最大的矩形）和 LeetCode 496（下一个更大元素）。单调队列则把单调性维护扩展到了双端，两端都能操作，适合处理窗口滑动的场景。
这两种数据结构共同的核心思想是：利用你已经有的大小关系，跳过那些“永远不可能成为答案”的候选者。柱状图最大矩形中，一旦遇到一个比栈顶短的柱子，短柱子右侧的矩形范围就确定了，比它高的柱子都可以弹出并结算；滑动窗口最大值中，新元素比队尾大，队尾就永远没机会成最大值，直接弹出。
如果你理解了这个“淘汰无用候选者”的思想，你会发现它不只是算法题的道具，在很多实际优化场景里都成立。比如实时排行榜维护、网络流量监控窗口的峰值计算、传感器数据流中的异常峰值检测，本质上都是同一套逻辑：维护一个动态更新、有过期机制的候选集合。
5.3 一个进阶题：绝对差不超过限制的最长连续子数组
LeetCode 1438 是一道把单调队列用得很妙的题：“绝对差不超过限制的最长连续子数组”。题目要求找最长连续子数组，使得子数组内任意两个元素的差的绝对值不超过 limit。
这题需要同时维护窗口内的最大值和最小值，差值超过 limit 时就收缩窗口左边界。用两个单调队列分别存最大值候选和最小值候选，左边界移动时同步清理两队中过期的索引。这里单调队列的价值在于：你不需要每次收缩左边界后重新扫描整个窗口找最大最小值，直接从两个队列头部取值就行，均摊复杂度依然是 O(n)。
这道题比 239 多了一个窗口长度不固定的变化，但核心还是“双端队列维护窗口极值 + 索引过期清理”，一通百通。如果你想检验自己是不是真的理解了单调队列，可以拿 1438 练手。
6. 面试现场：怎么把一个解讲成加分项
6.1 先讲朴素解，再抛出优化思路，展示思考过程
面试官出这道题，通常不只是想让你默写代码。他们更在意的是你面对问题时怎么思考：能不能从暴力解出发，找到重复计算的瓶颈，再设计数据结构去消除冗余。
一个比较稳健的答题节奏是：
第一句话先说暴力解：“最直接的方法是每个窗口扫描一次，复杂度 O(n×k)，但这个在数据量大时不可接受。”
第二句话指出瓶颈：“相邻窗口有 k-1 个重叠元素，暴力解把这些元素重复比较了。”
第三句话抛出思路：“我可以用一个单调递减的双端队列来维护候选最大值，每次窗口移动时只做三个 O(1) 操作——新元素入队时淘汰队尾小于等于它的元素、检查队头是否过期、记录队头作为结果。”
这样讲，面试官能清晰看到你的思维链条，而不是看到你背了一道题。即使他追问“为什么用双端队列而不是普通队列”，你也能顺理成章地解释：队尾要弹出小值、队头要弹出过期值，普通队列只有一头能操作，做不到。
6.2 手写代码的节奏和注释细节
面试手写代码时，有几个习惯很加分：
先写注释说明队列里存什么：// dq 存储数组下标，对应值从队头到队尾递减。这一句话就能让面试官快速进入你的代码逻辑，也能防止自己写着写着忘了队列的含义。
变量名尽量直观。我见过有人用q、s、t这种单字母命名，虽然代码短，但别人读起来很费劲。用dq（deque）和res（result）就够了。
在四个关键步骤前写上数字步骤注释：
// 1. 队尾维护单调递减 // 2. 新元素入队 // 3. 队头清理过期 // 4. 窗口完整后记录结果这种注释不是写给别人看的，是帮你自己在写代码时保持步骤清晰。面试时边写边小声说思路，也能让面试官跟上你的节奏。
写完代码后，一定要主动提出“我拿刚才的例子过一遍”。拿题目自带的示例跑一遍流程，如果发现某一步不对，当场调整。面试官更看重你调试问题的过程，而不是一个完美的默写结果。
6.3 追问环节的高频问题应对思路
这道题的追问点其实很固定。提前准备一下，答起来就很从容。
问：“为什么不用优先队列？”
答：优先队列也可以，代码更短，但堆操作是 O(log k)，整体 O(n log n)。单调队列能让每个元素最多进出一次，达到 O(n)。面试场景我会先说堆是保底方案，但单调队列在数据量更大时性能更优，所以最终选它。
问：“如果数组是流式数据、不可预知长度呢？”
答：这正好是单调队列更适合的场景。流式输入时窗口每来一个元素就处理一次，单调队列均摊 O(1) 的维护成本非常适合实时处理。优先队列在流式场景下需要额外的惰性删除机制，反而复杂。
问：“如果窗口大小是变化的呢？”
答：单调队列里过期检查的条件从左边界固定变成动态更新即可，队列结构本身不需要改变。这在 LeetCode 1438 这类题里已经体现了。
问：“如果要求的是窗口中第二大的值呢？”
答：那单调队列就不够用了，可能需要线段树或者平衡树。但面试到这里你其实可以坦诚说“这需要更高级的数据结构”，并且话锋一转，说出为什么单调队列只能维护极值——因为它淘汰了所有非极值候选，第二大的信息已经被丢弃了。能说出这个边界，本身就展示了你对数据结构的理解深度。
我个人在面试中特别认同一个做法：不要等面试官把追问抛完才回应，而是自己主动把“为什么不用堆”“流式输入怎么办”这些问题作为补充讲出来。面试官每天面很多人，听的都是差不多的答案，你主动多讲一层，就比其他人多展示一层深度。这道题你如果能把单调队列的“淘汰逻辑”和堆的“惰性删除”对比着讲，已经能超过大多数候选人了。
