题目
给你一个整数数组
nums 和滑动窗口大小
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
字节大数据方向面经原题（还有"流式数据 + TopK"的加码变体）。
一、核心洞察：只留还有机会的候选
先看清这题（LC 239）的规模：暴力每窗扫一遍是
O(n·k)，
k = n/2 时退化为平方。想线性，就得想办法
不重复比较。
观察一个例子：窗口滑到
[3, -1] 时，队列里存着
3 和
-1；下一个来了
5 ——
-1 和
3 还有可能成为未来某个窗口的最大值吗？
不可能。只要 5 还在窗口里，-1 和 3 就永远轮不到 —— 5 比它们大，又比它们晚离开窗口（5 出窗时它们早出窗了）。被"又大又晚"的新元素压住，就是被支配，可以永久淘汰。
这就是单调队列的全部思想：
队列里只留"还有机会当最大值"的候选，并按值递减排列 —— 队首自然恒为当前窗口最大。每来一个新元素，把队尾所有被它支配的元素扔掉，自己入队。
淘汰的判据是"不小于"（
<=）而不是"小于"：相等的旧元素也留不得 —— 留着不增加信息（值一样），还多占一位。淘汰后队列
严格递减，这个"严格"后面还有用（见 9.5）。
二、拆解：两个独立的维护动作
每来一个元素
x = nums[i]，只做两件事：
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # 存下标！对应值严格递减
ans = []
for i, x in enumerate(nums):
# 动作一：队首淘汰（出窗）—— 看下标
if dq and dq[0] < i - k + 1:
dq.popleft()
# 动作二：队尾淘汰（被支配）—— 看值
while dq and nums[dq[-1]] <= x:
dq.pop()
dq.append(i)
if i >= k - 1:
ans.append(nums[dq[0]])
return ans
三个要点：
- 队列存下标，不存值。动作一要判断"这个元素还在不在窗口里"，只有下标能回答（
dq[0] < i - k + 1）—— 存值的话这个判断根本没法做。这是本题最经典的实现错误；
- 两个动作互相独立：动作一看下标（时间维度：你出窗了吗），动作二看值（空间维度：你被支配了吗）。一个从队首出、一个从队尾出，各自循环；
- 答案就是队首。队列严格递减、且所有下标都在窗内 —— 队首必然是最大值，不需要任何额外扫描。
注意动作一用
if 还是
while 都行（每步窗口只左移一位，队首最多过期一个），但动作二必须是
while（可能连续支配多个）。
三、动画怎么看
动画四行：
- 数组行：淡金底 = 当前窗口（下方色带标
L/R），当前元素橙框；本帧被支配的格子画橙虚线边、值变灰 —— "还在窗里但已经没机会了"；滑出左端的格子灰虚；
- 队列行：单调队列的当前内容（值 +
#下标 小字），最左格绿框 = 队首（最大值）；被支配/出窗的元素不出现在这里 —— 它们已经永久离场；
- 答案行：已收集的窗口最大值，刚记录的一格金色；
- record 帧：窗口装满
k 个时单独一帧，横幅给出"队首 X 就是这一窗的最大值"。
主例的教科书帧是
i = 4（值 5）：队首
#1(3) 出窗（动作一），队尾
-3、
-1 被 5 支配（动作二）—— 一次滑动同时触发两个动作，队列从 3 个元素直接缩成 1 个。
四、完整推演表
以
[1,3,-1,-3,5,3,6,7]、
k = 3 为主例：
注意帧 2：
1 被
3 支配 —— 此后任何包含
3 的窗口里
1 都不是最大，它确实再也没有回来过。帧 5 是两个动作同时触发的教科书帧。
五、变体：堆、块状 DP 与大数据加码
5.1 堆 + 惰性删除（O(n log n)）
大顶堆存
(值, 下标)；窗口滑动时
不急着删过期的堆顶，只在取答案时检查堆顶下标是否还在窗内，过期就
pop（惰性删除）：
import heapq
def maxSlidingWindow(nums, k):
h, ans = [], []
for i, x in enumerate(nums):
heapq.heappush(h, (-x, i)) # Python 堆是小顶，取负变最大
if i >= k - 1:
while h[0][1] < i - k + 1: # 堆顶已出窗 → 惰性弹出
heapq.heappop(h)
ans.append(-h[0][0])
return ans
O(n log n)，比单调队列慢，但
写起来快、不易错，且天然支持"任意时刻查询前 m 大"这类扩展。面试给出对比：单调队列快但只回答"窗口最大"；堆慢一点但信息多。
5.2 块状 DP（不出名的线性做法）
把数组按
k 分块，
left[i] = 从块左到 i 的最大值，
right[i] = 从 i 到块右的最大值（两个方向各扫一遍）。窗口
[l, l+k-1] 的最大值 =
max(right[l], left[l+k-1]) —— 两个"部分块"的最大值拼接。严格
O(n)、无均摊分析，缺点是不直观、扩展性差。知道存在即可。
5.3 大数据加码（字节面经原题的延伸）
- 数据流：元素一条条来，随时查询"最近 k 个的最大值" —— 单调队列天然就是流式的，
deque + 一个计数即可；
- 窗口最大值的 TopK：滑动过程中维护的队列本身就是"候选列表"，配合计数结构可扩展；
- 数据量超内存：分块 + 归并（每块内部单调队列，块间取 max），本质是 5.2 的分布式版 —— 面试官想听的是"分块让局部性成立，块间归并 O(块数)"。
5.4 同族题
家族口诀：
"新来的把旧的压死"就上单调栈/队列 —— 想要答案"从一端取"用队列（滑窗），想要"每个元素的下一个更大"用栈。单调性淘汰的都是永久出局者，所以均摊 O(1)。
六、Java 版
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] ans = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque(); // 存下标，值严格递减
for (int i = 0; i < n; i++) {
if (!dq.isEmpty() && dq.peekFirst() < i - k + 1) {
dq.pollFirst(); // 动作一：队首出窗
}
while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
dq.pollLast(); // 动作二：队尾被支配
}
dq.offerLast(i);
if (i >= k - 1) {
ans[i - k + 1] = nums[dq.peekFirst()];
}
}
return ans;
}
ArrayDeque 当单调队列用：
peekFirst/pollFirst 管队首（出窗），
peekLast/pollLast 管队尾（支配）。
七、边界情况
八、复杂度
- 时间 O(n)：每个元素最多入队一次、出队一次 —— while 看着像嵌套，实际是均摊 O(1)。
- 空间 O(k)：队列里最多 k 个下标（下标都在窗内且严格递增）。
对照：暴力 O(n·k)；堆 O(n log n) + O(n) 空间；块状 DP O(n) + O(n) 空间。单调队列三项全优，代价是想清楚"支配"这个不变量。
九、常见坑
9.1 队列存值不存下标
存值就没法判断队首"还在不在窗里" ——
dq[0] < i - k + 1 这个比较对象是下标。
存下标，值随手可查（
nums[dq[0]]）。这是本题翻车率最高的实现错误。
9.2 队首出窗的时机
在读答案
之后才弹出过期队首 → 本窗答案可能是早就滑出去的元素。顺序：先维护（出窗 + 支配），再 push，再读答案。（把动作一写成
while 也无害，但
if 就够 —— 每步窗口只移一位。）
9.3 队尾判据写成 <（严格小于）
nums[dq[-1]] < x 时相等的元素会留在队列里 —— 值一样、下标更老，留着不增加任何信息，还会让队列"非严格递减"，极端输入（全相等）退化。用
<=，保证
严格递减。
9.4 忘了 k > n / 空数组
k > n 时没有有效窗口；不提前拒绝的话
i >= k - 1 永远不触发，倒也能返回空 —— 但答案是
碰巧对，入口处一行
if k > n: return [] 才是把"结构上不可能"说明白。
9.5 以为 while 嵌套是 O(n·k)
队尾 while 看着像两层循环，实际每个元素至多被 pop 一次（入队次数只有 n）—— 这是
均摊分析，面试要能主动讲出"入队一次出队一次"这笔账，否则会被追问"为什么不是平方"。
9.6 堆解法忘了惰性删除的边界
while h[0][1] < i - k + 1 的
< 和窗口定义必须一致（左闭
[i-k+1, i]）；写成
<= 会把刚过期的合法堆顶也弹掉。堆解法的所有下标比较都要和窗口左端对齐。
十、面试怎么答
- 一句话定性："队列里只留还有机会当最大值的候选，按值递减 —— 队首恒为最大；被支配的元素永久淘汰。"
- 先讲清"支配"：右边出现不小于它的元素 = 又大又晚，永远轮不到 —— 这是"为什么敢扔"的正确性论证，比代码值钱。
- 报出两个独立动作："队尾看值（单调性）、队首看下标（出窗）—— 所以队列必须存下标。"
- 主动给均摊分析："每元素入队一次出队一次，总 O(n) —— while 不是嵌套。"
- 对比表：暴力 O(n·k)、堆 O(n log n)、块状 DP O(n)、单调队列 O(n)/O(k) —— 各自的扩展性（堆支持任意查询、块状适合分布式）。
- 大数据加码：流式场景单调队列天然在线；超内存就分块 + 归并。
结语
滑动窗口最大值是单调结构的定型题：
"被支配即永久淘汰"这一条不变量，同时解释了正确性（扔掉的确实没用）和复杂度（每个元素只死一次）。上一题 LC 20 的栈、这一题的队列、之前 LC 42 的单调栈，全是同一条思想的三个化身 —— 区别只在"从哪一端取答案"。把"支配"讲清楚，这一族题就都通了。