演算法面試：如何用單調佇列求滑動視窗最大值？

題幹與適用場景

給定整數陣列 nums 和視窗大小 k。視窗先涵蓋索引 0 到 k - 1，接著每次向右移動一格；回傳每個 視窗的最大值。限制為 1 <= nums.length <= 100000、1 <= k <= nums.length。例如：

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
結果 = [3, 3, 5, 5, 6, 7]

目標時間複雜度為 O(n)，輸出陣列以外的額外空間為 O(k)。標準題目保證陣列非空且 k 有效；如果正式 API 需要接受空陣列或非法 k，應先另外定義回傳值或例外，不能把未約定行為混進演算法證明。

2026 年多份中英文演算法面試材料仍把 Sliding Window Maximum 列為單調雙端佇列的直接練習，並要求說明 隊首、過期索引、隊尾淘汰與攤銷複雜度。中文公開題解也在 2026 年繼續比較暴力與雙端佇列方案。本題屬於 通用演算法與資料結構能力，準確分類為 coding，不因範例使用 TypeScript 而歸入前端。

面試官考察點

第一，能否辨識「視窗每次只進一個、出一個，卻要持續求極值」的結構。暴力法把相鄰視窗中重複的 k - 1 個元素重新掃描；單調佇列只保留仍可能成為目前或未來最大值的候選索引。

第二，是否能解釋為什麼儲存索引而非只存數值。視窗過期由位置決定；相同數值可能來自不同位置。沒有索引， 就無法可靠判斷隊首最大值是否已經離開視窗。

第三，能否證明隊尾元素可以永久刪除。若較舊元素 nums[j] 不大於新元素 nums[i] 且 j < i，新元素更大 或相等，又更晚離開視窗；只要兩者同時存在，舊元素就不可能勝出。這是支配關係，不是為了讓佇列「看起來有序」。

最後，複雜度是否使用攤銷分析。某一輪可能連續彈出多個索引，單輪並非嚴格 O(1)；但每個索引只入隊一次， 也最多從隊首或隊尾離隊一次，所以全部雙端佇列操作為 O(n)。

回答前需要釐清的問題

• 視窗長度固定嗎？ 本題固定為 k；可變視窗需要重新定義過期條件和查詢介面。
• 陣列是否可能為空？ 標準限制排除空陣列；若擴充介面允許空輸入，應明確回傳空陣列或拒絕。
• k 是否保證有效？ 本題保證有效；示範實作仍做執行期檢查，避免負長度結果或越界存取。
• 元素能否重複或為負數？ 可以。演算法只依賴比較與索引，不依賴正數或互異性。
• 相同值應保留新索引還是舊索引？ 兩者都能得到正確最大值；本文刪除舊的相等值，保留較晚過期的新索引。
• 空間是否真的要求 O(k)？ 是。只移動陣列頭指標卻不回收舊槽位的 JavaScript 實作可能實際保留 O(n) 儲存；本文使用容量為 k 的環形緩衝區。
• 只回傳最大值還是最大值索引？ 主問題回傳值；若需要索引，直接輸出隊首索引，並另外定義重複最大值的選擇規則。
• 是否允許修改輸入陣列？ 不允許；實作只讀取 nums。

30 秒回答框架

「我會用雙端佇列儲存候選索引，並維持索引從隊首到隊尾遞增、對應值嚴格遞減。處理索引 i 時，先從隊首 刪除不在目前視窗內的索引；再從隊尾刪除值小於等於 nums[i] 的索引，因為新元素至少一樣大且會更晚過期， 舊元素不可能再成為最大值。然後把 i 入隊。第一個完整視窗形成後，隊首對應值就是答案。每個索引入隊一次、 最多離隊一次，因此總時間 O(n)；佇列最多儲存 k 個索引，額外空間 O(k)。」

分步驟深入解答

第一步：用基礎方案找出重複工作。

當 n 和 k 都接近 100000 時，暴力法可能進行約 10^10 次比較。heap 是容易說明的過渡方案，但它維護 所有元素間的優先順序；題目每次只讀最大值，保留被更新元素支配的舊候選沒有價值。

第二步：把「無用元素」寫成支配規則。

假設 j < i 且 nums[j] <= nums[i]。在任何同時包含 j 和 i 的未來視窗中，j 的值不會超過 i； 當視窗繼續右移時，j 還會先於 i 過期。因此從 i 到達的時刻起，j 永遠不可能再次成為視窗最大值， 可以從候選集合永久刪除。

刪除條件使用小於等於，代表相等值只保留最新索引，佇列值嚴格遞減。若只刪除更小值也仍然正確，但佇列值 只是非遞增，並會保留多個相等候選。兩種策略不能在證明和程式碼裡混用。

第三步：維護四個可檢查的不變條件。

處理完索引 i 後：

1. 佇列中的索引嚴格遞增，順序與到達順序一致。
2. 佇列中的索引都在目前範圍 [i - k + 1, i] 內。
3. 從隊首到隊尾，對應陣列值嚴格遞減。
4. 目前視窗中每個被刪除的索引，都有一個更晚且不小於它的候選留在支配鏈上。

前三條說明隊首是保留候選中的最大值；第四條說明被刪元素不會讓真實最大值消失。兩部分合起來，隊首才能 代表整個視窗，而不只是佇列內部的最大值。

第四步：實作實際占用 O(k) 的環形雙端佇列。

export function maxSlidingWindow(
  nums: readonly number[],
  k: number,
): number[] {
  if (!Number.isInteger(k) || k < 1 || k > nums.length) {
    throw new RangeError("k must be an integer between 1 and nums.length");
  }

  const deque = new Int32Array(k);
  let head = 0;
  let size = 0;
  const result: number[] = [];

  for (let i = 0; i < nums.length; i += 1) {
    while (size > 0 && deque[head] <= i - k) {
      head = (head + 1) % k;
      size -= 1;
    }

    while (size > 0) {
      const back = (head + size - 1) % k;
      if (nums[deque[back]] > nums[i]) break;
      size -= 1;
    }

    deque[(head + size) % k] = i;
    size += 1;

    if (i >= k - 1) {
      result.push(nums[deque[head]]);
    }
  }

  return result;
}

環形緩衝區容量恰好為 k。每輪入隊前，過期元素已經刪除，因此目前視窗最多已有 k - 1 個有效索引， 寫入不會覆蓋隊首。Int32Array 足以儲存最多 100000 的索引；如果題目允許超過 32 位範圍的索引，應改用 一般數值陣列或重新限制輸入。

第五步：證明演算法回傳每個視窗的真實最大值。

初始化時佇列為空，不變條件成立。處理新索引時，隊首刪除只移除視窗之外的元素，所以不影響目前答案。隊尾 刪除依據支配規則：每個被刪元素都有更新且不小於它的 i 取代。把 i 加到隊尾後，索引繼續遞增，值繼續 嚴格遞減。

第一個完整視窗在 i = k - 1 形成。此後每輪隊首都在視窗內；佇列值嚴格遞減使隊首大於其餘候選，而支配鏈 保證任何未保留元素都不可能大於某個保留元素。因此 nums[deque[head]] 等於目前視窗最大值。對所有 i 歸納，輸出的 n - k + 1 個值都正確。

第六步：走查重複值和過期邊界。

對範例，括號中記錄「索引:值」：

i=0  [0:1]                  未形成視窗
i=1  [1:3]                  3 支配 1
i=2  [1:3, 2:-1]            輸出 3
i=3  [1:3, 2:-1, 3:-3]      輸出 3
i=4  [4:5]                  1 過期，5 支配 -1 和 -3，輸出 5
i=5  [4:5, 5:3]             輸出 5
i=6  [6:6]                  6 支配 5 和 3，輸出 6
i=7  [7:7]                  7 支配 6，輸出 7

陣列 [4, 4, 4]、k = 2 時，第二個 4 會刪除第一個 4，第三個再刪除第二個；佇列始終只有最新索引，兩個 視窗仍都輸出 4。這個例子能檢查相等值條件，也能發現只存值時無法判斷過期的問題。

第七步：準確給出攤銷複雜度。

迴圈有兩個 while，不能據此相乘成 O(nk)。每個索引只入隊一次；離隊後不會回來，因此所有隊首彈出和 隊尾彈出的總次數不超過 n。總時間為 O(n)。環形佇列最多儲存 k 個索引，額外空間為 O(k)；結果陣列 有 n - k + 1 個元素，通常不計入額外空間。

第八步：用樸素 oracle 做差異測試。

固定案例涵蓋：k = 1、k = n、全相等、嚴格遞增、嚴格遞減、全負數和標準混合範例。空陣列與 k = 0 屬於非法輸入，預期拋出 RangeError。再產生短隨機陣列與隨機有效 k，把結果和「逐視窗掃描最大值」的 樸素實作逐項比較；隨機測試同時檢查結果長度與每個視窗的隊首值。

當 n 很小或只計算一個視窗時，暴力掃描更短、更容易審查；當語言已經提供可靠雙端佇列時，應優先沿用標準 容器。本文寫環形緩衝區，是為了讓 TypeScript 範例的實際記憶體界限與 O(k) 分析一致。

高品質示範回答

「暴力法會為每個視窗掃描 k 個元素，最壞是 O(nk)。我會維護一個儲存索引的單調雙端佇列。佇列索引 按到達順序遞增，對應值從隊首到隊尾嚴格遞減。

處理索引 i 時，先刪除隊首所有不大於 i - k 的過期索引。然後從隊尾刪除值小於等於 nums[i] 的索引： 新元素至少一樣大，而且更晚離開視窗，所以舊元素不可能再成為最大值。接著把 i 放到隊尾；當 i >= k - 1 時，隊首就是目前視窗最大值。

正確性依賴兩點：被隊首刪除的元素已經不在視窗內；被隊尾刪除的元素都有一個更新、不小於它且存活更久的 元素取代。佇列保持值遞減，所以剩餘候選的最大值在隊首。每個索引入隊一次、最多離隊一次，總操作數為 線性，因此時間 O(n)；佇列最多儲存 k 個索引，額外空間 O(k)。我會重點測試 k = 1、k = n、 重複值、單調陣列和負數，並用暴力實作做隨機差異測試。」

常見錯誤

• 佇列只存數值 → 相同值無法判斷哪一個過期 → 儲存索引，透過陣列讀取值。
• 只維護遞減值，不刪除過期隊首 → 已離開視窗的舊最大值會繼續被輸出 → 每輪先依 i - k 清理隊首。
• 把過期條件寫成小於 i - k → 索引恰為 i - k 的元素已在視窗左側之外 → 使用小於等於。
• 看到內層 while 就聲稱 O(nk) → 同一索引不會反覆彈出 → 用每個索引至多入隊、離隊一次做攤銷分析。
• 使用 shift() 並聲稱操作為常數時間 → JavaScript 陣列頭刪可能移動元素 → 使用標準 deque、頭指標或環形緩衝區。
• 頭指標只增不回收卻聲稱空間 O(k) → 舊槽位仍可能讓底層陣列成長到 O(n) → 使用容量固定為 k 的環形儲存。
• 相等值的彈出規則與證明不一致 → 「嚴格遞減」和「非遞增」被混用 → 明確本文用小於等於刪除舊值。
• heap 裡只存值 → 延遲刪除仍無法識別過期元素 → heap 方案也必須儲存索引。
• 只跑標準範例 → k = 1、重複值和遞減陣列中的邊界錯誤未暴露 → 加入固定邊界和隨機 oracle。

追問及應對

追問一：為什麼相等時刪除舊索引仍然安全？

新索引的值相等，而且一定比舊索引晚過期。在兩者共存的所有視窗中，留下任意一個都能提供相同最大值；舊 索引先離開，不會在新索引過期後重新獲得機會。因此保留新索引即可，也能縮短佇列。

追問二：如果還要回傳每個最大值第一次出現的索引呢？

相等值不能再刪除舊索引；隊尾只刪除嚴格更小的值，使佇列值非遞增。這樣隊首保留目前視窗中最早的最大值。 若要求最後一次出現，則沿用本文刪除小於等於的規則。回傳規則改變了相等值策略，但不改變 O(n) 界限。

追問三：為什麼不用最大 heap？

heap 可以更快寫出，使用值與索引並延遲刪除後能得到正確答案；普通二元 heap 中的過期元素若不在 heap 頂， 會繼續占用空間，最壞可成長到 O(n)，時間為 O(n log n)。支援任意刪除的索引 heap 可控制為 O(n log k) 和 O(k)，但實作更複雜。若面試只要求先給可用方案，heap 可以作為過渡，再最佳化為單調佇列。

追問四：視窗同時需要最大值和最小值怎麼辦？

維護兩個獨立雙端佇列：一個對應值遞減，隊首給最大值；另一個對應值遞增，隊首給最小值。每個索引在每個 佇列中仍然只入隊和離隊一次，所以總時間仍為 O(n)，額外空間為 O(k)。

追問五：如果每次視窗大小都會變化呢？

若左右邊界仍單調向右移動，可以用目前左邊界清理過期索引，單調佇列仍適用；若視窗會向左擴張，先前永久 刪除的候選可能重新進入範圍，目前結構無法復原它們。此時應改用平衡樹、線段樹或離線 RMQ，並依更新與 查詢模式選擇複雜度。

追問六：資料是無限串流，如何線上輸出？

為每個到達元素分配遞增序號，執行相同的過期和隊尾刪除；從第 k 個元素開始，每到一個元素立即輸出一次 隊首值。只保留最多 k 個候選索引和值，記憶體與串流總長度無關。若上游會亂序到達，還需先定義事件時間 視窗、水位和遲到策略，這已經不是本題的順序陣列模型。

追問七：如何把方法推廣到受限動態規劃？

若轉移形如「目前位置狀態等於自身代價加上前 k 個狀態的最大值」，可以讓佇列依 DP 值遞減，隊首提供 轉移所需最大值，過期條件仍由索引決定。差別是比較對象從 nums[i] 變成 dp[i]；證明仍依賴更晚且不小的 狀態支配舊狀態。