Monotonic Queue單調佇列
滑動視窗中 O(1) 取最大值。
用在：即時監控的視窗極值、DP 優化
01為什麼需要它
每秒進來一個數字，隨時要報「最近 60 筆的最大值」。每次重新掃 60 筆是 O(k)，一天八萬六千秒乘上 k，而且 k 常常是幾千。
為什麼用它單調佇列讓視窗滑動時，取最大值是 O(1)。每個數字只進出佇列各一次，整體 O(n)，和 k 無關。
對圖片每個像素取周圍 k×k 範圍的最大值（膨脹運算）。直接做是 O(n·k²)。
為什麼用它先對每一列做一維的滑動視窗最大值，再對每一行做一次，兩次 O(n)。單調佇列是這類「視窗極值」的標準工具。
很多 DP 的轉移長這樣：dp[i] = max(dp[j]) + 某個值，其中 j 在 [i−k, i−1] 之間。每個 i 都掃一遍 j 是 O(nk)。
為什麼用它「區間內的最大值」隨 i 滑動，正是單調佇列處理的形狀，把轉移壓成 O(1)。這是進階 DP 常見的優化。
看到這些關鍵字就想到它：滑動視窗的最大／最小值、固定長度區間的極值、最近 k 個、視窗滑動時極值怎麼更新、DP 轉移的區間 max。
02核心概念
單調佇列是一個雙端佇列，裡面的值從前到後保持遞減（求最大值時），所以最前面永遠是目前視窗的最大值。它同時用到 deque 的兩端：尾端負責維持單調性，前端負責把離開視窗的元素淘汰。
核心觀察：新元素 x 進來時，尾端所有比 x 小的元素可以直接丟掉。理由是它們比 x 小，又比 x 早進視窗、會比 x 早離開，所以只要 x 還在，它們永遠當不上最大值。丟掉之後把 x 放到尾端，佇列自然保持遞減。
前端則要檢查是否已經滑出視窗：存的是索引，若 dq[0] ≤ i − k 就從前端彈出。因為每個索引只推入一次、彈出至多一次，n 個元素總共 O(n)，比暴力的 O(nk) 和堆積的 O(n log k) 都好。
它和單調堆疊的關係：都靠「新元素進來前把沒用的彈掉」維持單調性。差別在單調佇列還要從前端淘汰過期的，所以需要 deque。凡是「在一個滑動的區間裡取極值」，先想它。
03演算法步驟
- 1建一個 deque 存索引（不是值，才能判斷是否過期）。求最大值時維持值遞減，求最小值時遞增。
- 2對每個 i：先清尾端，
while dq and nums[dq[-1]] <= nums[i]: dq.pop()。用<=讓相等的舊元素也被淘汰，佇列更短。 - 3把 i 推入尾端。
- 4再清前端：
if dq[0] <= i − k: dq.popleft()。每一輪最多只會過期一個，所以用 if 就夠。 - 5當
i ≥ k − 1（視窗滿了），nums[dq[0]]就是這個視窗的答案。
04互動示範
視窗大小 3。每一步先從尾端彈掉比新元素小的（劃掉的），再檢查前端是否過期；綠色是 deque 最前面，也就是目前視窗的最大值。
05程式碼
滑動視窗最大值與最小值只差一個比較符號；第三段把前綴和和單調佇列組合起來解「和至少為 k 的最短子陣列」，是這個技巧的進階用法。
from collections import deque
# 滑動視窗最大值（LeetCode 239）
# deque 存索引，對應的值從前到後遞減，最前面永遠是視窗最大值
def max_sliding_window(nums, k):
dq = deque()
out = []
for i, x in enumerate(nums):
while dq and nums[dq[-1]] <= x: # 尾端比 x 小的永遠不會再是最大值
dq.pop()
dq.append(i)
if dq[0] <= i - k: # 最前面已經離開視窗
dq.popleft()
if i >= k - 1: # 視窗滿了才輸出
out.append(nums[dq[0]])
return out
# 同一個骨架改成最小值：把 <= 換成 >=
def min_sliding_window(nums, k):
dq = deque()
out = []
for i, x in enumerate(nums):
while dq and nums[dq[-1]] >= x:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
out.append(nums[dq[0]])
return out
# 和至少為 k 的最短子陣列（LeetCode 862）：前綴和 + 單調佇列
def shortest_subarray(nums, k):
p = [0]
for x in nums:
p.append(p[-1] + x)
dq = deque() # 前綴和遞增的索引
best = float("inf")
for j, pj in enumerate(p):
while dq and pj - p[dq[0]] >= k: # 前端能當左端點就結算，之後不會更好
best = min(best, j - dq.popleft())
while dq and p[dq[-1]] >= pj: # 尾端比我大的，當左端點永遠輸我
dq.pop()
dq.append(j)
return best if best != float("inf") else -106練習題
- LeetCode 239Sliding Window MaximumHard
- LeetCode 1438Longest Continuous Subarray With Absolute Diff ≤ Limit（同時維護 max 與 min）Medium
- LeetCode 862Shortest Subarray with Sum at Least KHard
- LeetCode 1696Jump Game VI（DP + 單調佇列）Medium
- LeetCode 1425Constrained Subsequence SumHard