題目描述

給定一個數組 nums 和滑動窗口的大小 k，請找出所有滑動窗口里的最大值。

• 你可以假設 k 總是有效的，在輸入數組不為空的情況下，1 ≤ k ≤ 輸入數組的大小。

題目樣例

示例

輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7]
解釋:

  滑動窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

題目思考

1. 如果要求時間復雜度為 O(N), 該如何做?

解決方案

思路

• 一個比較容易想到的思路是暴力法, 即固定每個起點, 然后求它之后 k 個元素的最大值并依次加入結果中, 這樣時間復雜度為 O(Nk), 當 k 很大的時候效率非常低, 該如何提高效率呢?
• 重新觀察題目示例, 如果我們能夠動態維護當前窗口的最大值, 那么在窗口移動的時候只需要用 O(1)時間返回這個值即可
• 窗口右移的時候, 如果新加入的值比原來的最大值還要大的話就好辦, 直接更新最大值即可
• 但問題來了, 窗口右移意味著左邊界也要向右移動, 如果正好之前的左邊界是最大值該如何處理呢? 顯然只保存最大值一個變量是不夠的, 我們也需要保存第二大值, 第三大值...
• 根據上面的分析, 我們需要把這些值保存在一個單調的數據結構中, 一邊是窗口里的最大值, 另一邊則是最小值
• 窗口右移的時候, 按照順序分為三部分操作:
1. (當加入當前值后窗口長度會超過 k 時, 即                          right>=k) 移除老的左邊界值:                          如果它恰好是最大值, 也移除單調數據結構中對應的值
2. 加入新的右邊界值: 此時需要先不斷移除最小值, 直到當前新值成為新的最小值再插入, 因為更小的值絕不可能成為最大值的候選項(                          又舊, 值又小)
3. (當加入當前值后窗口長度達到 k 時, 即                          right>=k-1) 將單調數據結構中保存的最大值加入最終結果中
• 注意上述三個步驟中 3 必須是最后一步, 因為要先調整完當前窗口的最大最小值才行, 而 1 和 2 可以互換位置, 因為可以先處理左邊界, 也可以先處理右邊界
• 根據上述過程, 我們只需要處理頭和尾的插入刪除操作, 很顯然                         雙端隊列就是最合適的數據結構, 兩種操作都只需要 O(1)時間
• 下面代碼對必要的步驟有詳細的解釋, 特別是對步驟 1 和 2 的一些關鍵點的解釋, 方便大家理解

復雜度

• 時間復雜度 O(N): 每個值最多加入和移出雙端隊列各一次, 總共 2N 次操作, 所以時間復雜度是 O(N)
• 空間復雜度 O(k): 雙端隊列最多存 k 個值

代碼

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 單調雙端隊列, 左邊存窗口最小值, 右邊存窗口最大值
        q = collections.deque()
        res = []
        left = 0
        for right in range(len(nums)):
            # 步驟1 (當加入當前值后窗口長度會超過 k 時, 即right>=k) - 移除老的左邊界值: 如果它恰好是最大值, 也移除隊列尾
            # 注意左邊界如果不是最大值的話, 不會存在于隊列中, 因為它后面總有更大的值將左邊界從隊列中淘汰出去 (步驟2的操作)
            if right >= k:
                if nums[left] == q[-1]:
                    q.pop()
                left += 1
            # 步驟2 (可以和步驟1互換位置) - 加入新的右邊界值: 此時需要先不斷移除隊列左側最小值, 直到當前新值成為新的最小值再插入左側, 因為更小的值絕不可能成為最大值的候選項(又舊, 值又小)
            # 注意這里需要是小于而不能是小于等于, 因為如果當最小值等于當前值且都被移除的話, 如果它恰好也是最大值, 那么下次移除左邊界的時候就會錯誤地將當前的值給移除, 而不是移除左邊界對應的那個值, 這樣會導致后面的最大值計算出現錯誤
            while q and q[0] < nums[right]:
                q.popleft()
            q.appendleft(nums[right])
            # 步驟3 (當加入當前值后窗口長度達到 k 時, 即right>=k-1) - 將隊列右側最大值加入最終結果中
            if right >= k - 1:
                res.append(q[-1])
        return res