单调队列：滑动窗口最大值
摘要
单调队列（Monotonic Deque）是在双端队列（Deque）上施加单调性约束的数据结构，专为解决”滑动窗口内的极值”问题而生。本篇以 LeetCode 239（Sliding Window Maximum）为核心，系统讲解单调队列的设计思路、操作规则与实现细节：用一个从头到尾单调递减的双端队列维护窗口状态，队头始终是当前窗口的最大值。时间复杂度 ，每个元素最多入队一次、出队一次。文章还将对比朴素堆方案（）与单调队列方案（）的差异，并探讨单调队列在 DP 优化中的扩展应用。
第 1 章 问题引入与朴素思路
1.1 题目
LeetCode 239 - Sliding Window Maximum（困难）
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
输入: nums = [1,3,-1,-3,5,3,6,7], k = 3
输出: [3,3,5,5,6,7]
窗口位置 最大值
[1 3 -1] -3 5 3 6 7 → 3
1 [3 -1 -3] 5 3 6 7 → 3
1 3 [-1 -3 5] 3 6 7 → 5
1 3 -1 [-3 5 3] 6 7 → 5
1 3 -1 -3 [5 3 6] 7 → 6
1 3 -1 -3 5 [3 6 7] → 7
1.2 暴力
// 每次窗口移动后，线性扫描找最大值
for (int i = k - 1; i < n; i++) {
int max = nums[i];
for (int j = i - k + 1; j < i; j++) max = Math.max(max, nums[j]);
result[i - k + 1] = max;
}时间 ， 时接近 次操作，超时。
1.3 堆方案
维护一个大小为 k 的最大堆：每次窗口滑动时移除最左侧元素，加入新元素，查询堆顶即为最大值。
问题：标准堆不支持 删除任意元素（只能删堆顶）。处理方式：使用”惰性删除”（lazy deletion）——堆中的元素用 (value, index) 对存储，每次 peek 时检查堆顶的 index 是否还在窗口内，若不在则弹出。
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] result = new int[n - k + 1];
// 最大堆，按值降序，值相同按下标降序（可以任意排序下标）
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] != b[0] ? b[0] - a[0] : b[1] - a[1]);
for (int i = 0; i < n; i++) {
heap.offer(new int[]{nums[i], i});
// 弹出窗口外的元素
while (heap.peek()[1] <= i - k) heap.poll();
// 窗口填满后，记录结果
if (i >= k - 1) result[i - k + 1] = heap.peek()[0];
}
return result;
}时间 （堆中可能有 个惰性删除的元素），空间 。已经可以通过 LeetCode，但不是最优解。
第 2 章 单调队列： 的最优解
2.1 核心洞察
关键观察：如果窗口内存在两个元素，位置 i < j，且 nums[i] <= nums[j]，那么 i 永远不可能成为任何包含 j 的窗口的最大值（j 在 i 右边，且 j 的值不更小）。
换句话说，在窗口向右移动的过程中，被更右边更大的元素”盖住”的元素可以直接丢弃。
这让我们可以维护一个从头到尾单调递减的双端队列：队头始终是窗口的最大值。
2.2 单调递减队列的操作规则
入队操作（每次新元素 nums[i] 进入窗口）：
- 从队尾移除所有小于等于
nums[i]的元素（它们被nums[i]永久”盖住”，无用） - 将
i加入队尾
出队操作（窗口左侧元素离开）：
- 检查队头的下标是否已经滑出窗口（
queue.peek() <= i - k） - 若是，从队头移除
查询操作：队头 queue.peekFirst() 的下标对应的值即为当前窗口最大值。
2.3 代码实现
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] result = new int[n - k + 1];
// 双端队列，存储下标，保持对应值从头到尾单调递减
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
// 1. 移除队尾中所有值 <= nums[i] 的元素（它们被当前元素"盖住"，永远不会是最大值）
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
// 2. 当前下标入队
deque.offerLast(i);
// 3. 移除已经滑出窗口的队头元素（下标 <= i - k）
if (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
// 4. 窗口填满后，记录结果
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}2.4 逐步模拟
nums = [1,3,-1,-3,5,3,6,7], k=3
deque 中存下标，| 前是队头
i=0, nums[0]=1:
deque空，直接入队: deque=[|0]
i<k-1, 不记录
i=1, nums[1]=3:
nums[0]=1 <= 3, 移除 0: deque=[]
入队 1: deque=[|1]
i<k-1, 不记录
i=2, nums[2]=-1:
nums[1]=3 > -1，不移除
入队 2: deque=[|1,2]
i=k-1=2: result[0]=nums[deque.peekFirst()=1]=nums[1]=3 ✓
i=3, nums[3]=-3:
nums[2]=-1 > -3，不移除
入队 3: deque=[|1,2,3]
队头1, 1<=3-3=0? 否
result[1]=nums[1]=3 ✓
i=4, nums[4]=5:
nums[3]=-3 <= 5, 移除 3
nums[2]=-1 <= 5, 移除 2
nums[1]=3 <= 5, 移除 1
deque=[], 入队 4: deque=[|4]
队头4, 4<=4-3=1? 否
result[2]=nums[4]=5 ✓
i=5, nums[5]=3:
nums[4]=5 > 3，不移除
入队 5: deque=[|4,5]
队头4, 4<=5-3=2? 否
result[3]=nums[4]=5 ✓
i=6, nums[6]=6:
nums[5]=3 <= 6, 移除 5
nums[4]=5 <= 6, 移除 4
deque=[], 入队 6: deque=[|6]
队头6, 6<=6-3=3? 否
result[4]=nums[6]=6 ✓
i=7, nums[7]=7:
nums[6]=6 <= 7, 移除 6
deque=[], 入队 7: deque=[|7]
队头7, 7<=7-3=4? 否
result[5]=nums[7]=7 ✓
最终: result=[3,3,5,5,6,7] ✓
2.5 复杂度分析
时间 ：每个元素最多被压入队列一次（offerLast），被弹出队列一次（pollLast 或 pollFirst）。虽然内层 while 循环会多次执行，但总弹出次数不超过 ，摊还到每个元素是 。
空间 ：队列中最多有 k 个元素（一个窗口的大小）。
与堆方案对比：
| 方案 | 时间 | 空间 | 实现复杂度 |
|---|---|---|---|
| 暴力 | 简单 | ||
| 堆 + 惰性删除 | 中等 | ||
| 单调队列 | 中等 |
第 3 章 单调队列 vs 单调栈
单调栈和单调队列看起来相似，但解决的问题和操作规则不同：
| 特性 | 单调栈 | 单调队列 |
|---|---|---|
| 底层结构 | 栈（一端进出） | 双端队列（两端都可操作） |
| 解决的问题 | ”下一个更大/更小元素”，前后边界 | ”窗口内的极值” |
| 元素的生命周期 | 弹出后永久消失 | 弹出后因”超出窗口”而消失，可以从两端弹出 |
| 主要操作 | 从同一端入栈和弹栈 | 从队尾入队，从队头（超出窗口）或队尾（被覆盖）弹出 |
关键区别：单调队列需要从两端操作：
- 从队尾删除被新元素”盖住”的旧元素（入队前的清理）
- 从队头删除超出窗口的过期元素
这正是为什么必须用双端队列（Deque），而不是普通队列或栈。
第 4 章 单调队列的进阶应用
4.1 单调队列优化 DP
单调队列最重要的进阶应用是 DP 优化：当 DP 的状态转移方程中，某个维度上的转移是从一段连续下标的最值推导的，单调队列可以将 的转移优化到 ，总复杂度从 降到 。
典型例子：跳跃游戏（LeetCode 1696 - Jump Game VI）
dp[i] = nums[i] + max(dp[j]), 其中 i - k <= j < i
这是一个”过去 k 步内的 dp 最大值”，正是滑动窗口最大值的结构，用单调队列维护 dp[j] 的滑动窗口最大值：
public int maxResult(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
Deque<Integer> deque = new ArrayDeque<>();
deque.offerLast(0);
for (int i = 1; i < n; i++) {
// 移除超出 k 步范围的队头
while (!deque.isEmpty() && deque.peekFirst() < i - k) {
deque.pollFirst();
}
// 队头是最大 dp 值的下标
dp[i] = nums[i] + dp[deque.peekFirst()];
// 维护单调递减队列
while (!deque.isEmpty() && dp[deque.peekLast()] <= dp[i]) {
deque.pollLast();
}
deque.offerLast(i);
}
return dp[n - 1];
}这个模式在竞赛算法中非常常见，俗称”单调队列 DP 优化”或”deque DP”。
4.2 相关变体题目
| 题目 | 变体 | 核心修改 |
|---|---|---|
| LeetCode 239（本题） | 滑动窗口最大值 | 标准模板 |
| LeetCode 862（最短的含正和子数组） | 滑动窗口 + 前缀和 | 单调递增队列（找最小前缀和） |
| LeetCode 1696（Jump Game VI） | DP 优化 | 单调队列维护 DP 值 |
| LeetCode 918（环形子数组的最大和） | 循环数组 | 先求前缀和，再用单调队列 |
第 5 章 实战细节与面试建议
5.1 入队条件：严格 < 还是 <=
// 移除被"盖住"的元素时，用 <= 还是 <？
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}这里用 <= 而不是 <：若有相等元素，保留更新的（更右边的）下标，因为更旧的下标更快离开窗口，没有存在价值。
如果用 <，相等元素都留在队列里，只是会有冗余元素，不影响正确性（队头仍是最大值），但会让队列不必要地变大。两种写法都可以通过 LeetCode 239，但 <= 更规范。
5.2 易错点：出队检查的时机
// 先入队，再检查出队；还是先检查出队，再入队？
// 正确做法：先入队（从队尾），再检查队头是否超出窗口
deque.offerLast(i);
if (deque.peekFirst() <= i - k) deque.pollFirst();如果先检查队头再入队，不影响正确性；但”先入后检查”的逻辑更清晰——入队时处理队尾（单调性维护），检查队头时处理窗口过期，职责分离。
5.3 面试中如何讲清楚
单调队列是”信息量很大、代码很短”的类型，面试官最想听到的是为何可以丢弃某些元素。建议这样表述：
“如果一个元素在某个窗口内，它的右边有一个比它大的元素，那么这个左边的元素永远不可能是任何包含右边那个元素的窗口的最大值——因为右边元素会在更晚的窗口才离开，在此之前每个包含左边元素的窗口也必然包含右边元素，右边元素更大。所以左边元素可以安全丢弃。”
这段话说清楚了”为什么丢弃是安全的”，是面试中区分”只会背模板”和”真正理解”的关键。
下一篇预告
07 字符串嵌套解码与基本计算器 是本专栏的收尾篇，用两道题综合展示栈在字符串解析中的应用。LeetCode 394（Decode String）是 k[encoded_string] 格式的递归展开，栈用来保存当前层的前缀字符串和重复次数，是”保存现场，处理嵌套”的栈应用模型；LeetCode 224（Basic Calculator）是带括号和加减法的表达式求值，栈用来保存括号前的计算结果和符号状态，是字符串解析中最复杂的栈应用场景之一。