# 单调队列图解：滑动窗口最大值与两种出队

滑动窗口最大值为什么能在线性时间求出？通过带符号柱形、窗口平移与双端队列动画，同步理解过期删除、支配删除、重复值和摊还分析。

原文 / Canonical: https://crazycloud.cc/learn/monotonic-queue
作者: crazycloudcc
首次发布: 2026-10-28
更新: 2026-10-28

本阅读版与网页共用课程数据；互动请访问原文。

## 一句话答案

单调队列保存候选下标。窗口右移时先从队首删除过期下标，再从队尾删除不大于新值的候选，最后加入新下标。清理后下标递增、值严格递减，队首就是当前窗口最大值；窗口满 k 项才输出。

## 适用条件与边界

固定长度 k 的连续窗口，1≤k≤n。纯求解器接受非空稠密安全整数数组（拒绝负零），只比较值、不做值的算术。教学轨迹限制 n≤16、|A[i]|≤10⁶；预设包含负数、相等、递增、递减及 k=1、k=n。

## 不变量

每次 append 完成后，队列下标在当前窗口内且递增，对应值严格递减；被删除的非过期项均有更晚且不小的替代者。arrive 和清理中间步骤尚未保证完整不变量。

## 逐步例子

1. 原创例子 A=[5,2,4,1,3,6,2]，k=3。完整窗口最大值依次为 [5,4,4,6,6]。
2. 新下标 i 到达后，左边界是 max(0,i−k+1)。队首下标≤i−k 已过期，即使值最大也必须从左端删除。到达阶段尚未清理，不能提前读最大值。
3. 从右端删除 A[队尾]≤A[i] 的候选。若旧下标 j<i，未来仍包含 j 的窗口也包含 i；新值不小且过期更晚，j 永远不会优于 i。
4. 加入 i 后，下标严格递增、对应值严格递减。i≥k−1 才输出队首值；之前窗口未满，不输出部分窗口答案。
5. 相等值采用≤删除，保留较新下标。改用严格<也可以正确求最大值，但会保留重复值，须始终用下标处理过期。
6. k=1 时每项都是答案；k=n 时只输出一次；递减输入保留最多 k 个候选；全负数仍直接取队首值，不以0兜底。

## 摊还复杂度与教学轨迹

真正求解器使用容量 k 的环形数组，每个下标恰入队一次、最多出队一次，总 O(n) 时间、O(k) 辅助空间，输出另占 O(n−k+1)。单次到达可能弹出 O(k) 项，不能说每次都严格 O(1)。教学轨迹为了任意回看复制队列及累计输出，最多 O(n²) 时间和空间，不能拿它宣称线性求解性能。

## 常见误区

- 只存值，无法分辨重复值与过期下标
- 到达后未清理就读队首，或窗口未满提前输出
- 把一次大量弹出误判成总 O(nk)，或把每一步误称最坏 O(1)
- 用0初始化全负数窗口的最大值
- 用数组 shift 实现大规模队列却仍宣称严格线性实现

## 自测

新值与队尾相等时，为什么保留新下标？

新旧值一样大，新下标过期更晚。未来窗口若还包含旧下标，就也包含新下标，因此删除旧下标不影响最大值。

## 参考资料

- [LeetCode 239：Sliding Window Maximum（问题定义）](https://leetcode.com/problems/sliding-window-maximum/)
- [CSES：Sliding Window Minimum（最小值、生成序列与 XOR 变体；非本课完整实现）](https://cses.fi/problemset/task/3221)

[返回图解实验室](https://crazycloud.cc/learn)