 优化到 O(n)？)
LeetCode 239「滑动窗口最大值」，是Hard难度的经典题，也是各大厂面试的高频题。
给你一个数组和窗口大小k，窗口每滑一步，就要立刻知道窗口内的最大值。
暴力：每个窗口遍历一遍 → O(nk)，n=1e5 时直接炸 大顶堆：取最大值O(log k)，但删除“离开窗口”的元素很麻烦，得懒删除 + 堆顶清理，代码复杂且易错 单调队列：每个元素入队出队各一次，O(n) 搞定，而且代码干净利落
现在不只给你能AC的代码，更给你一套“单调递减双端队列”的通用框架。以后遇到“滑动窗口最值”类问题，你都能用同样的套路——队尾弹小，队首弹旧，队首即答案。
📦 题目速览（30 秒读懂）
给定数组
nums和窗口大小k，窗口从左向右滑动，返回每个窗口的最大值。示例：
nums = [1,3,-1,-3,5,3,6,7],k=3
输出：[3,3,5,5,6,7]约束：n ≤ 1e5，暴力 O(nk) 必挂。
🧠 核心思路：用单调递减队列“淘汰”永远不可能成为最大值的元素
暴力到底慢在哪里？
每个窗口独立求最大值，完全不利用上一个窗口的信息。
窗口每次只变一个元素（出去一个，进来一个），但暴力把所有 k 个元素重新扫一遍。
关键观察（单调性的威力）
假设窗口内有两个元素nums[i]和nums[j]，且i < j（j 在 i 右边）。如果nums[i] <= nums[j]，那么nums[i]永远不可能成为任何后续窗口的最大值——因为nums[j]比它大，而且nums[j]会留在窗口中比nums[i]更久。
所以我们可以维护一个单调递减的队列（存索引）：
从队尾入队时，把所有比新元素小的旧元素全部弹出（它们已无价值） 从队首取最大值前，检查队首是否已经滑出窗口（过期则弹出） 队首永远是当前窗口的最大值
每个元素最多入队一次、出队一次，总操作O(2n)，均摊O(1)。
🖼️ 图解全过程（手把手走一遍）
nums = [1, 3, -1, -3, 5, 3, 6, 7],k=3，队列存索引：
| i | 新元素 | 操作（队尾弹出小的，队首弹出过期的） | 队列（索引→值） | 窗口范围 | 最大值 |
|---|---|---|---|---|---|
| 0 | 1 | 入队 | [0→1] | 未满 | — |
| 1 | 3 | 1<3，弹出0，入队1 | [1→3] | 未满 | — |
| 2 | -1 | 入队 | [1→3, 2→-1] | [0,2] | 3 |
| 3 | -3 | 入队 | [1→3,2→-1,3→-3] | [1,3] | 3 |
| 4 | 5 | 弹出3(-3)、2(-1)、1(3)，入队4 | [4→5] | [2,4] | 5 |
| 5 | 3 | 入队 | [4→5, 5→3] | [3,5] | 5 |
| 6 | 6 | 弹出5(3)、4(5)，入队6 | [6→6] | [4,6] | 6 |
| 7 | 7 | 弹出6(6)，入队7 | [7→7] | [5,7] | 7 |
注意：i=3 时队首索引1仍有效（1 ≥ 3-3+1=1），所以未过期。
关键点：新元素5入队时，把前面所有比它小的（3,-1,-3）全部弹出，因为它们再也不可能当最大值了。队列始终保持从队首到队尾严格递减。
💻 代码实现
Python 版
fromcollectionsimportdeque
classSolution:
defmaxSlidingWindow(self, nums: List[int], k: int)-> List[int]:
dq = deque()# 存索引，队首→队尾 递减
ans = []
fori, valinenumerate(nums):
# 1. 队首过期：索引 < i-k+1 的弹出
whiledqanddq[0] < i - k +1:
dq.popleft()
# 2. 队尾维护：弹出所有比当前值小的元素
whiledqandnums[dq[-1]] < val:
dq.pop()
# 3. 当前索引入队
dq.append(i)
# 4. 当窗口满时，队首即为最大值
ifi >= k -1:
ans.append(nums[dq[0]])
returnans
Java 版
classSolution{
publicint[] maxSlidingWindow(int[] nums,intk) {
Deque<Integer> dq =newArrayDeque<>();// 存索引
int[] ans =newint[nums.length - k +1];
intidx =0;
for(inti =0; i < nums.length; i++) {
// 1. 弹出过期队首
while(!dq.isEmpty() && dq.peekFirst() < i - k +1) {
dq.pollFirst();
}
// 2. 弹出队尾小于当前值的元素
while(!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
dq.pollLast();
}
// 3. 入队
dq.offerLast(i);
// 4. 取结果
if(i >= k -1) {
ans[idx++] = nums[dq.peekFirst()];
}
}
returnans;
}
}
⚠️致命坑（必看）：
队列里存的是索引，不是值！这样才能判断过期（ dq[0] < i-k+1）。两个 while 的顺序：先弹过期队首，再弹队尾小元素，最后入队。顺序不能乱。 比较时用 <还是<=：一般用<，相等时保留旧元素，不影响正确性且减少操作。
⏱️ 复杂度分析（面试必问）
时间：每个元素最多入队一次、出队一次，总操作O(2n)，均摊O(1) →O(n) 空间：双端队列最多存k个元素 →O(k)（不计返回结果）
🚀 举一反三：4 道高频变种题，一套框架通吃
| 题目 | 差异点 | 应对策略 |
|---|---|---|
| LeetCode 1438. 绝对差不超过限制的最长连续子数组 | 需要同时维护最大值和最小值 | 用两个单调队列（一个递减、一个递增），窗口内max-min超限时移动左边界 |
| LeetCode 862. 和至少为K的最短子数组 | 前缀和 + 单调队列（递增） | 队列存前缀和索引，维护单调递增，以找到满足条件的最短子数组 |
| LeetCode 1499. 满足不等式的最大值 | 二维坐标 + 单调队列优化 | 维护队列中y - x的单调递减，结合滑动窗口 |
| LeetCode 1696. 跳跃游戏 VI | 跳跃得分最大化 | 单调队列维护前k步内的最大得分，O(n)动态规划优化 |
💬 面试追问模拟（提前准备，惊艳全场）
Q1：为什么不用优先队列（大顶堆）？
优先队列取最大值O(log k)，但删除“离开窗口”的元素很麻烦：堆不支持任意位置删除，只能“懒删除” —— 在堆顶检查元素是否过期，过期则弹出。
这样每次可能弹掉多个过期元素，摊还也是O(nlogk)。而单调队列直接利用单调性，队首就是最大值，过期队首也在队首，删除O(1)，总O(n)。性能更优，代码也更简洁。
Q2：队列里存索引而不存值，为什么？
因为需要知道每个元素在数组中的位置，才能判断它是否已经滑出窗口（即
index < i-k+1）。如果只存值，无法判断过期。存索引后，通过nums[dq[0]]取值即可。
Q3：如果窗口需要同时取最大值和最小值，怎么做？
维护两个双端队列：一个单调递减（队首最大），一个单调递增（队首最小）。在每次滑动时，分别维护两个队列，然后可以同时得到最大值和最小值。LC.1438 就是这种场景。
Q4：单调队列和单调栈有什么区别？
维度 单调队列 单调栈 数据结构 双端队列（两端操作） 栈（一端操作） 出队/出栈条件 队首按窗口过期弹出 栈顶按遍历结束弹出 典型应用 滑动窗口最值 下一个更大/更小元素 元素进出次数 每个最多一次 每个最多一次
🧩 实战小技巧（刷题党必备）
口诀：队尾弹小（保持递减），队首弹旧（窗口过期），队首即答案。 模板：凡是“滑动窗口内求最值”类问题，优先想到单调队列。 调试：打印队列内索引和对应值，观察是否严格递减。 边界： k=1时每个窗口只有自身，单调队列也适用；k=n时只有一个窗口，队首即为全局最大值。
📈 实际应用场景（不止是刷题）
量化交易：滑动时间窗口内找股票最高价/最低价 网络监控：实时统计最近 N 秒内的流量峰值 图像处理：滑动窗口最大值滤波（形态学膨胀操作） 日志分析：滚动时间窗口内检测异常峰值 游戏排行榜：统计每个时间段内的最高分
🎁 今日思考题
如果把题目改为“滑动窗口最小值”，代码需要改几行？
只需将nums[dq[-1]] < val改为>（即保持单调递增），其他完全相同。如果同时求最大和最小，你能写出维护两个队列的框架吗？
