基本資料#
難易度: hard 第一次嘗試： 2025-08-02
- 總花費時間：00:00.00
解題思路#
這道題是我第一次使用雙端佇列（deque）。概念是維護一個雙端佇列，保持固定窗口內數字的排序。關鍵洞察是如果佇列中的元素小於我們正在迭代的元素，我們可以將其彈出，因為如果窗口中出現更大的元素，在尋找範圍內最大數字時，較小的元素就變得無用。我們如何確保佇列中的元素都在範圍內？我們將索引存儲在佇列中，並在每一步檢查第一個元素，如果索引已經超出範圍，我們就將其彈出。由於我們在每次迭代中都這樣做，我們總能維持佇列在當前窗口內。
解法#
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = deque()
res = []
for i in range(len(nums)):
while q and nums[q[-1]] < nums[i]:
q.pop()
if q and q[0] <= (i - k):
q.popleft()
q.append(i)
if i - k + 1 >= 0:
res.append(nums[q[0]])
return res
收穫#
單調雙端佇列技巧: 這道題介紹了強大的單調雙端佇列技巧，我們維護一個雙端佇列，按對應值的遞減順序存儲索引。這確保雙端佇列的前端始終包含當前窗口中的最大值。
高效的最大值追蹤: 通過維護單調遞減的雙端佇列，我們可以在 O(1) 時間內訪問任何時刻的最大值，這比需要 O(k) 時間在每個窗口中尋找最大值的樸素方法要高效得多。
基於索引的方法: 在雙端佇列中存儲索引而不是值至關重要，因為它允許我們確定元素何時落在當前窗口之外並需要被移除。
窗口邊界管理: 條件
q[0] <= (i - k)確保我們移除不再在當前窗口內的元素，維持滑動窗口的特性。單調性維護: while 迴圈
while q and nums[q[-1]] < nums[i]通過移除在未來窗口中永遠不會成為最大值的小元素來維持單調遞減特性。時間複雜度: O(n)，其中 n 是輸入陣列的長度。雖然我們有巢狀迴圈，但每個元素最多被推入和彈出一次，導致每個元素的攤銷 O(1) 操作。
空間複雜度: 最壞情況下為 O(k)，其中 k 是窗口大小，因為雙端佇列最多可以包含 k 個元素。
遇到的問題#
理解單調雙端佇列: 最初，我難以理解為什麼我們可以安全地從雙端佇列中移除較小的元素。關鍵洞察是如果出現更大的元素，在它之前出現的較小元素在未來任何窗口中永遠不會成為最大值。
索引與值存儲: 我對是否在雙端佇列中存儲索引或值感到困惑。存儲索引是必要的，因為我們需要知道元素何時落在當前窗口之外。
雙端佇列操作順序: 操作的順序（彈出較小元素，移除窗口外元素，追加當前元素）對於維持雙端佇列的正確狀態至關重要。