滑动窗口最大值

给定数组 a 和窗口大小 k，依次输出每个长度为 k 的子数组的最大值。朴素做法是每个窗口扫一遍，O(n·k)。用单调队列可以压到 O(n)。

单调队列思路

维护一个 deque，里面只保存当前窗口里的有用候选——按下标递增、对应的值严格递减。这样队首永远是当前窗口的最大值。

每移动到一个新位置 i：

1. 清理队首：如果队首索引已经离开窗口（< i - k + 1），弹掉
2. 清理队尾：从队尾开始弹出所有 a[?] ≤ a[i] 的索引——它们既比 a[i] 小又更早，永远不可能是后续窗口的最大值
3. 入队：把 i 压到队尾
4. 取答案：如果窗口已经成型（i ≥ k - 1），队首索引对应的值就是当前窗口的最大

每个索引最多入队、出队各一次，总共 O(n) 次操作。

复杂度

• 时间：O(n)
• 空间：O(k)（deque 最多装 k 个候选）

在动画里看什么

• 数组上方的虚线框是当前窗口 [i - k + 1, i]
• 深蓝单元格是刚处理的 a[i]；浅蓝是当前在 deque 里的有用候选
• 下方的 deque 中，暖红色的就是窗口最大值（队首）
• result 在每次窗口成型时追加一个值