单调队列 (Sliding Window Max/Min)

引言：“滚动最值”问题

你正在监控一个实时数据流。你需要显示 过去 60 秒内（一个滑动窗口）出现的最大值。每一秒钟，都会有一个新值进入，一个旧值离开。

如果每次都重新找最大值，每步耗时 $O(K)$（$K$ 是窗口大小）。对于 100 万个点的窗口，这根本行不通。单调队列 通过维护一种特殊的顺序，使最大值始终位于队首，实现每步 均摊 $O(1)$ 的性能。

算法要解决什么问题？

• 输入： 一个数字流和窗口大小 $K$。
• 输出： 随着窗口滑动，当前窗口内的最大/最小值。
• 承诺： 整个流程的处理时间为 $O(N)$，且与窗口大小 $K$ 无关。

核心思想 (直觉版)

想象一个 “优胜劣汰” 的队列：

1. 当一个新值进入时：它会从队尾“挑战”已经在队列里的值。
2. 如果新值比队尾的值 更大，那么旧值就没用了（只要这个更大、更新的值在窗口里，旧的小值永远不可能是最大值）。所以，我们 踢出 那些较小的旧值。
3. 队列保持 单调递减（最大的在最前面）。
4. 随着窗口滑动，我们还要检查队首元素是否已经“过期”（离开了窗口范围），如果是，则将其移除。

为什么要用它？

• ✅ 极致效率： 每个元素最多进队一次、出队一次。总工作量是 $2N$。
• ✅ 实时性： 非常适合需要立即得到结果的流式数据。

典型业务场景

• ✅ 实时图表： 在监控仪表盘中显示“最高水位线”或“最高延迟”。
• ✅ 交易系统： 计算过去 $N$ 個跳動點 (Ticks) 中的最高出价。
• ✅ 图像处理： 2D 滑动窗口滤波器（如卷積神經網絡中的最大池化 Max-pooling）。
• ✅ DP 优化： 许多动态规划问题可以通过单调队列将复杂度从 $O(N^2)$ 优化到 $O(N)$。

性能与复杂度总结

• 时间： 每元素均摊 $O(1)$。
• 空间： $O(K)$，$K$ 是窗口大小。

小结：一句话记住它

“单调队列是一个‘冷酷的过滤器’。它踢掉任何比新来者小的旧值，确保窗口的冠军永远坐在最前面。”