HardRating 1860
239. Sliding Window Maximum
arrayqueuesliding-windowheap-priority-queuemonotonic-queue
解題說明
Sliding Window Maximum
題目描述：
給定一個整數陣列 nums 和一個滑動窗口大小 k，窗口從陣列最左端滑動到最右端，每次向右移動一格。回傳每個窗口位置中的最大值所組成的陣列。
解題思路： 暴力解法對每個窗口掃描 k 個元素取最大值，時間 O(nk)。最優解利用單調遞減雙端佇列（Monotonic Deque），達到 O(n) 時間。
單調遞減雙端佇列：
雙端佇列（deque）中儲存的是元素的索引，且保持對應的值從頭到尾嚴格遞減。這樣佇列的頭部（front）永遠是當前窗口的最大值的索引。
對每個新元素 nums[i]，執行以下步驟：
- 彈出過期索引：若佇列頭部的索引已滑出窗口（即
deque.front() <= i - k），從頭部彈出。 - 維護遞減性：從尾部開始，若佇列尾部的值
<=當前值nums[i]，則從尾部彈出（因為那些元素在窗口內永遠不會成為最大值，可以捨棄）。 - 加入當前索引到尾部。
- 記錄最大值：當窗口已達到大小 k（即
i >= k - 1），將nums[deque.front()]加入結果。
關鍵洞察：被從尾部彈出的元素，由於有更大的 nums[i] 在其右方且在相同或更長的窗口內，所以它們永遠不會成為任何窗口的最大值，提前捨棄完全安全。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每個元素最多被加入佇列一次、從佇列彈出一次，無論從頭部還是尾部，總操作次數為 2n 次，因此整體為線性時間。
空間複雜度：O(k) — 雙端佇列中最多同時存放 k 個索引（一個完整窗口的候選值），輸出陣列不計入額外空間。
虛擬碼
1. Initialize an empty deque dq (stores indices) and result array. 2. For each index i from 0 to n-1: a. If dq is not empty and dq.front() <= i - k: pop from front (expired). b. While dq is not empty and nums[dq.back()] <= nums[i]: pop from back. c. Push i to the back of dq. d. If i >= k - 1: append nums[dq.front()] to result. 3. Return result.
其他解法
暴力法 O(nk)：對每個窗口位置，線性掃描 k 個元素找最大值。實作最簡單，但當 n 和 k 都很大時效率極差。
線段樹或稀疏表（Sparse Table）O(n log n) 或 O(n) 預處理 + O(1) 查詢：建立範圍最大值查詢（Range Maximum Query, RMQ）資料結構。稀疏表預處理 O(n log n)，每次查詢 O(1)，總時間 O(n log n)。這類方法更通用，但對本題而言單調佇列已是最優，且只需 O(k) 空間，實務上更常使用。
延伸思考
- 本題使用單調遞減佇列取窗口最大值，若改為求每個窗口的最小值，只需要改動哪一行程式碼？
- 單調佇列的概念也能應用於動態規劃最佳化。請舉出一個 DP 問題，說明如何用單調佇列將 O(nk) 的狀態轉移最佳化到 O(n)。
- 如果需要同時查詢每個窗口的最大值和最小值，你會如何修改或組合資料結構來處理？