單調棧解「下一個更大元素」，換成「每個視窗的最大值」就卡住了——差別不在資料，在於視窗會從左邊過期，而棧的左邊你碰不到。
為什麼需要它？暴力法到底慢在哪
給你一個陣列和一個視窗大小 k，要你回報每個視窗位置的最大值。最直覺的寫法：視窗往右滑一格，就把視窗裡 k 個數重掃一遍取最大。
問題在重掃。視窗滑了 n-k+1 次，每次掃 k 個，總共 O(nk)。k 小的時候沒感覺，但 k 一旦上千、陣列上百萬，這就是會讓你在面試現場被追問「還能更快嗎」的那種寫法。而且它慢得很冤：兩個相鄰視窗其實只差一個元素，大部分的比較你都在重複做。
單調佇列就是來砍掉這些重複的。它的承諾很硬：每個元素一生只進佇列一次、出佇列一次，於是總操作量是 2n，時間降到 O(n)。下面拆解它怎麼辦到。
核心洞察：什麼樣的人可以直接請走
先想清楚一件事——視窗裡不是每個元素都有資格當「未來的最大值」。判斷一個舊元素還有沒有希望，只要問兩個問題：
- 有沒有一個新元素比它大？
- 這個新元素是不是比它晚離開視窗？
如果兩個都成立，那個舊元素就永遠沒戲了。因為只要它還在視窗裡，那個又大又晚走的新人也一定在，最大值輪不到它；等到新人開始有機會出頭，它早就先滑出去了。這種人留著只是佔位子，進來的當下就可以請走。
arr = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
佇列裡存的是「還有希望奪冠的候選人」（用值表示，實際存索引）：
加 1 → [1]
加 3 → 3 比 1 大又比它晚走，1 出局 → [3]
加-1 → -1 比 3 小，還可能等 3 走掉後上位，留著 → [3, -1] 視窗 [0,2] 最大 = 3
加-3 → 同理留著 → [3, -1, -3] 視窗 [1,3] 最大 = 3
加 5 → 5 把 -3、-1、3 全蓋過，一路清空 → [5] 視窗 [2,4] 最大 = 5
加 3 → 3 比 5 小，留著 → [5, 3] 視窗 [3,5] 最大 = 5
加 6 → 6 蓋過 3、5 → [6] 視窗 [4,6] 最大 = 6
加 7 → 7 蓋過 6 → [7] 視窗 [5,7] 最大 = 7看出佇列的形狀了嗎？從頭到尾永遠遞減——這就是「單調」的由來。而頭部那個永遠是當前視窗的最大值，取答案是 O(1)。
為什麼是佇列，不是棧？
這是這個結構最容易被含糊帶過、卻最該講清楚的地方。視窗裡的元素會因為兩種完全不同的理由被淘汰：
- 被蓋過：新來一個更大又更晚走的，把尾端一票小的清掉——這發生在尾端。
- 過期：視窗往右滑，最左邊的元素時間到了，得滑出去——這發生在頭端。
一端進出的單調棧只能處理第一種。它解「下一個更大元素」為什麼夠用？因為那類問題沒有「從左邊過期」這回事，元素進了棧就一直待到被彈出，左邊你根本不需要碰。可是滑動視窗會過期，你必須能從頭端把老元素踢掉——兩端都要能動，這就是為什麼非佇列不可。準確講是雙端佇列（Deque）：尾端維護單調性、頭端處理過期與取答案。
把兩種淘汰對到 Deque 的兩端，程式就是照著抄：
// 每次新元素 nums[i] 進來時，對佇列做的三件事
// deque 存的是索引，維護「值遞減」
// 1. 頭端：踢掉已經滑出視窗的（過期）
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1)
deque.pollFirst();
// 2. 尾端：踢掉所有 <= 當前值的舊候選人（被蓋過）
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i])
deque.pollLast();
// 3. 自己排到尾端
deque.addLast(i);這三段就是單調佇列的全部。第 2 段是靈魂——它同時保證了兩件事：佇列維持遞減，而且被清掉的元素這輩子不會再回來。完整的滑動視窗最大值解法（怎麼收集每個視窗的答案、邊界怎麼抓）我不在這重寫一遍，那是視窗題的視角，留在 Deque 那篇。
O(n) 是怎麼攤出來的
新手看到那兩個 while 迴圈常會慌：「迴圈裡包迴圈，這不是 O(nk) 甚至 O(n²) 嗎？」
不是。訣竅在於看一個元素的一生，而不是盯著單次迴圈。任何一個元素：
- 被
addLast排進佇列，剛好一次。 - 被踢出去——不管是尾端被蓋過（
pollLast）還是頭端過期（pollFirst）——至多一次，而且踢出去就不再回來。
所以整個過程中，進佇列的動作總共 n 次，出佇列的動作至多 n 次，加起來 2n。那兩個 while 看起來嚇人，但它們消耗的是「別人之前排進去」的額度，全程加總被 2n 這條天花板鎖死。這種「單次可能很貴、但總量有上限」的計費方式就是攤還分析（amortized）：不保證每一步都便宜，但保證平均下來每個元素只花 O(1)。
| 暴力重掃 | 單調佇列 | |
|---|---|---|
| 時間 | O(nk) | O(n) |
| 空間 | O(1) | O(k) |
| 慢/貴在哪 | 相鄰視窗重複比較 | 每元素只進出各一次 |
空間換來的 O(n) 值不值？視窗越大差距越誇張——k 從 3 變 3000，暴力法慢一千倍，單調佇列文風不動。
它不只解滑動視窗
單調佇列真正的身價，是它能鑽進 DP 裡當加速器。很多 DP 的轉移長這樣：
dp[i] = max(dp[j]) + cost[i]，其中 j 限定在 [i-k, i-1]那個「j 只能取前面一段區間」本質上就是一個滑動的視窗，而你要的是視窗內的 max dp[j]。照定義寫是每個 i 都掃 k 個 j，又是 O(nk)；套上單調佇列維護視窗內最大的 dp[j]，整條 DP 直接降到 O(n)。這是競賽裡「單調佇列優化 DP」的固定套路——一旦你認得出「轉移點被關在一個會滑動的區間裡」，工具就已經在手上了。
🎬 互動視覺化：Union-Find／單調佇列／Skip List 動畫 — 看新元素進來時尾端那串小候選人怎麼被一次清空、頭端的過期元素怎麼滑走，遞減的形狀怎麼全程維持。「為什麼可以請走它」用看的比用讀的快多了。
單調棧管的是「誰在我後面」，單調佇列多管一件「誰該退場了」——多出來的那隻手，就是它值得單獨拿出來講的理由。
接下來往哪走
- Deque 雙端佇列 — 單調佇列的載體，滑動視窗最大值的完整解法在這篇裡
- Monotone Stack 單調棧 — 只從一端踢人的近親，看清「一端 vs 兩端」到底差在哪
- Sliding Window 滑動視窗 — 視窗技巧的全貌，單調佇列是它「求視窗極值」那一支的最優解