單調隊列 (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$ 是窗口大小。

小結：一句話記住它

「單調隊列是一個『冷酷的過濾器』。她踢掉任何比新來者小的舊值，確保窗口的冠軍永遠坐在最前面。」