图解实验室 / 进阶 · 18 分钟 · 算法
单调队列：哪些候选可以永远删掉？
窗口向右走，过期从队首删，被支配从队尾删。观察柱形与下标一起移动，而不只是背一串队列数字。
固定窗口 k = 3 · 双端候选轨道
步骤 1/24窗口 [0, 1) · 候选下标 [] · 已输出 []
下标 0、值 5 到达；窗口左边界移到 0。队列尚未清理，不能先读最大值。
for (let i = 0; i < a.length; i++) {为什么可以删？
旧下标 j < i 且 A[j] ≤ A[i]：未来仍包含 j 的窗口必然也包含 i，新值不小、过期更晚。删除 j 不会丢失未来最大值。相等时保留较新的下标。
一次到达可能删掉很多候选；但每个下标最多入队一次、出队一次。环形队列求解共 O(n) 时间、O(k) 辅助空间，答案另占 O(n−k+1)。上方教学轨迹复制队列与输出，不属于该线性求解器。
完整求解核心（输入已通过 1≤k≤n 与整数检查）
const ring = new Array(k), output = [];
let head = 0, size = 0;
for (let i = 0; i < a.length; i++) {
while (size && ring[head] <= i-k) {
head = (head+1) % k; size--;
}
while (size && a[ring[(head+size-1)%k]] <= a[i]) size--;
ring[(head+size)%k] = i; size++;
if (i >= k-1) output.push(a[ring[head]]);
}自测：为什么不能只按值删除？
递减数组里队首可能一直最大，但离开窗口后必须删除。队列存下标才能判断过期。全负数时也不能用 0 作为最大值的初始答案。
看完图，带走这些结论
单调队列保存候选下标。窗口右移时先从队首删除过期下标，再从队尾删除不大于新值的候选，最后加入新下标。清理后下标递增、值严格递减，队首就是当前窗口最大值；窗口满 k 项才输出。
适用条件与边界
固定长度 k 的连续窗口，1≤k≤n。纯求解器接受非空稠密安全整数数组（拒绝负零），只比较值、不做值的算术。教学轨迹限制 n≤16、|A[i]|≤10⁶；预设包含负数、相等、递增、递减及 k=1、k=n。
始终保持的规律
每次 append 完成后，队列下标在当前窗口内且递增，对应值严格递减；被删除的非过期项均有更晚且不小的替代者。arrive 和清理中间步骤尚未保证完整不变量。
逐步例子
- 原创例子 A=[5,2,4,1,3,6,2]，k=3。完整窗口最大值依次为 [5,4,4,6,6]。
- 新下标 i 到达后，左边界是 max(0,i−k+1)。队首下标≤i−k 已过期，即使值最大也必须从左端删除。到达阶段尚未清理，不能提前读最大值。
- 从右端删除 A[队尾]≤A[i] 的候选。若旧下标 j<i，未来仍包含 j 的窗口也包含 i；新值不小且过期更晚，j 永远不会优于 i。
- 加入 i 后，下标严格递增、对应值严格递减。i≥k−1 才输出队首值；之前窗口未满，不输出部分窗口答案。
- 相等值采用≤删除，保留较新下标。改用严格<也可以正确求最大值，但会保留重复值，须始终用下标处理过期。
- 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 实现大规模队列却仍宣称严格线性实现
自测与答案
新值与队尾相等时，为什么保留新下标？
新旧值一样大，新下标过期更晚。未来窗口若还包含旧下标，就也包含新下标，因此删除旧下标不影响最大值。