使用單調隊列解決 「滑動窗口最大值」 問題

• 2022 年 11 月 4 日
• 筆記
• 演算法

本文已收錄到  GitHub · AndroidFamily，有 Android 進階知識體系，歡迎 Star。技術和職場問題，請關注公眾號 [彭旭銳] 私信我提問。

前言

大家好，我是小彭。

在上一篇文章中，我們介紹了單調棧這種特殊的棧結構，單調棧是一種非常適合處理 「下一個更大元素問題」 的數據結構。今天，分享到單調棧的孿生兄弟 —— 單調隊列（Monotonic Queue）。類似地，單調隊列也是在隊列的基礎上增加了單調的性質（單調遞增或單調遞減）。那麼單調隊列是用來解決什麼問題的呢？

學習路線圖：

1. 單調隊列的典型問題

單調隊列是一種用來高效地解決 「滑動窗口最大值」 問題的數據結構。

舉個例子，給定一個整數數組，要求輸出數組中大小為 K 的窗口中的最大值，這就是窗口最大值問題。而如果窗口從最左側逐漸滑動到數組的最右端，要求輸出每次移動後的窗口最大值，這就是滑動窗口問題。這個問題同時也是 LeetCode 上的一道典型例題：LeetCode · 239. 滑動窗口最大值

LeetCode 例題

這個問題的暴力解法很容易想到：就是每次移動後遍歷整個滑動窗口找到最大值，單次遍歷的時間複雜度是 $O(k)$，整體的時間複雜度是 $O(n·k)$，空間複雜度是 $O(1)$。當然，暴力解法里的重複比較運算也是很明顯的，我們每次僅僅往窗口裡增加一個元素，都需要與窗口中所有元素對比找到最大值。

那麼，有沒有更高效的演算法呢？

滑動窗口最大值問題

或許，我們可以使用一個變數來記錄上一個窗口中的最大值，每增加一個新元素，只需要與這個 「最大值」 比較即可。

然而，窗口大小是固定的，每加入一個新元素後，也要剔除一個元素。如果剔除的元素正好是變數記錄的最大值，那說明這個值已經失效。我們還是需要花費 $O(k)$ 時間重新找出最大值。那還有更快的方法尋找最大值嗎？

2. 解題思路

我們先用 「空間換時間」 的通用思路梳理一下：

在暴力解法中，我們每移動一次窗口都需要遍歷整個窗口中的所有元素找出 「滑動窗口的最大值」。現在我們不這麼做，我們把滑動窗口中的所有元素快取到某種數據容器中，每次窗口滑動後也向容器增加一個新的元素，而容器的最大值就自然是滑動窗口的最大值。

現在，我們的問題已經發生轉變，問題變成了：「如何尋找數據容器中的最大值」。 另外，根據題目條件限制，這個容器是帶有約束的：因為窗口大小是固定的，所以每加入一個新元素後，必然也要剔除一個元素。 我們的數據容器也要滿足這個約束。 現在，我們把注意力集中在這個容器上，思考一下用什麼數據結構、用什麼演算法可以更高效地解決問題。由於這個容器是我們額外增加的，所以我們有足夠的操作空間。

先說結論：

• 方法 1 – 暴力： 遍歷整個數據容器中所有元素，單次操作的時間複雜度是 $O(k)$，整體時間複雜度是 $O(n·k)$；
• 方法 2 – 二叉堆： 不需要遍歷整個數據容器，可以用大頂堆維護容器的最大值，單次操作的時間複雜度是 $O(lgk)$，整體時間複雜度是 $O(n·lgk)$；
• 方法 3 – 雙端隊列： 我們發現二叉堆中很多中間元素是冗餘的，拉低了效率。我們可以在每處理一個元素時，可以先觀察容器中剛剛加入的元素，如果剛剛加入的元素小於當前元素，則直接將其丟棄（後進先出邏輯）。最先加入容器的元素，如果超出了滑動窗口的範圍，也直接將其丟棄（先進先出邏輯）。所以這個容器數據結構要用雙端隊列實現。因為每個元素最多只會入隊和出隊一次，所以整體的計算規模還是與數據規模成正比的，整體時間複雜度是 $O(n)$。

下面，我們先從優先隊列說起。

3. 優先隊列解法

尋找最值的問題第一反應要想到二叉堆。

我們可以維護一個大頂堆，初始時先把第一個滑動窗口中的前 $k – 1$ 個元素放入大頂堆。滑動窗口每移動一步，就把一個新的元素放入大頂堆。大頂堆會自動進行堆排序，堆頂的元素就是整個堆中 $k$ 個元素的最值。然而，這個最大值可能是失效的（不在滑動窗口的範圍內），我們要怎麼處理這個約束呢？

我們可以用一個小技巧：將元素的下標放入隊列中，用 nums[index] 比較元素大小，用 index 判斷元素有效性。 此時，每次取堆頂元素時，如果發現該元素的下標超出了窗口範圍，就直接丟棄。

題解

class Solution {
    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        // 結果數組
        val result = IntArray(nums.size - k + 1) {-1}
        // 大頂堆
        val heap = PriorityQueue<Int> { first, second ->
            nums[second] - nums[first]
        }
        for (index in nums.indices) {
            if (index < k - 1) {
                heap.offer(index)
                continue
            }
            heap.offer(index)
            // while：丟棄堆頂超出滑動窗口範圍的失效元素
            while (!heap.isEmpty() && heap.peek() < index - k + 1) {
                // 丟棄
                heap.poll()
            }
            // 堆頂元素就是最大值
            result[index - k + 1] = nums[heap.peek()]
        }
        return result
    }
}

我們來分析優先隊列解法的複雜度：

• 時間複雜度： 最壞情況下（遞增序列），所有元素都被添加到優先隊列里，優先隊列的單次操作時間複雜度是 $O(lgn)$，所以整體時間複雜度是 $O(n·lgn)$；
• 空間複雜度： 使用了額外的優先順序隊列，所以整體的時間複雜度是 $O(n)$。

優先隊列解法的時間複雜度從 $O(n·k)$ 變成 $O(n·lgn)$，這個效果很難讓人滿意，有更好的辦法嗎？

我們繼續分析發現，由於滑動窗口是從左往右移動的，所以當一個元素 $nums[i]$ 的後面出現一個更大的元素 $nums[j]$，那麼 $nums[i]$ 就永遠不可能是滑動窗口的最大值了，我們可以永久地將它剔除掉。然而，在優先隊列中，失去價值的 $nums[i]$ 會一直存儲在隊列中，從而拉低了優先隊列的效率。

4. 單調隊列解法

我們可以維護一個數據容器，第一個元素先放到容器中，後續每處理一個元素，先觀察容器中剛剛加入的元素，如果剛剛加入的元素小於當前元素，則直接將其丟棄（因為新增加的元素排在後面，會更晚地離開滑動窗口，所以中間的小元素永遠沒有資格了），避免拉低效率。

繼續分析我們還發現：

• 這個數據容器中後進入的元素需要先彈出與當前元素對比，符合 「後進先出」 邏輯，所以這個數據結構要用棧；
• 這個數據容器中先進入的元素需要先彈出丟棄（離開滑動窗口），符合 「先進先出」 邏輯，所以這個數據結構要用隊列；

因此，這個數據結構同時具備棧和隊列的特點，是需要同時在兩端操作的雙端隊列。這個問題也可以形象化地思考：把數字想像為有 「重量」 的的杠鈴片，滑動窗口每移動一次後，新增加的大杠鈴片會把中間小的杠鈴片壓扁，後續不再考慮它們。

形象化思考

題解

class Solution {
    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        // 結果數組
        val result = IntArray(nums.size - k + 1) { -1 }
        // 單調隊列（基於雙端隊列）
        val queue = LinkedList<Int>()
        for (index in nums.indices) {
            // while：隊尾元素比當前元素小，說明隊尾元素不再可能是最大值，後續不再考慮它
            while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[index]) {
                // 拋棄隊尾元素
                queue.pollLast()
            }
            queue.offerLast(index)
            if (index < k - 1) {
                continue
            }
            // if：移除隊頭超出滑動窗口範圍的元素
            if (!queue.isEmpty() && queue.peekFirst() < index - k + 1) {
                queue.pollFirst()
            }
            // 從隊頭取目標元素
            result[index - k + 1] = nums[queue.peekFirst()]
        }
        return result
    }
}

單調隊列與單調棧的思路是非常類似的，單調棧在每次遍歷中，會將棧頂 「被壓扁的小杠鈴片」 彈出棧，而單調隊列在每次遍歷中，會將隊尾中 「被壓扁的小杠鈴片」 彈出隊。 單調棧在棧頂過濾無效元素，在棧頂獲取目標元素，單調隊列在隊尾過濾無效元素，在隊頭獲取目標元素。

理解了單調隊列的解題模板後，我們來分析它的複雜度：

• 時間複雜度： 雖然程式碼中有嵌套循環，但它的時間複雜度並不是 $O(n^2)$，而是 $O(n)$。因為每個元素最多只會入棧和出棧一次，所以整體的計算規模還是與數據規模成正比的，整體時間複雜度是 $O(n)$；
• 空間複雜度： 最壞情況下（遞增序列），所有元素被添加到隊列中，所以空間複雜度是 $O(n)$。

5. 單調棧、單調隊列、優先隊列對比

5.1 單調棧與單調隊列的選擇

單調隊列和單調棧在很大程度上是類似的，它們均是在原有數據結構的基礎上增加的單調的性質。那麼，什麼時候使用單調棧，什麼時候使用單調隊列呢？ 主要看你的演算法中元素被排除的順序，如果先進入集合的元素先排除，那麼使用棧（LIFO）；如果先進入集合的元素後排除，那麼使用隊列（FIFO）。 在例題中，甚至出現了同時結合棧和隊列的情況。

上一篇文章里我們討論過單調棧，單調棧是一種非常適合解決 」下一個更大元素「 的數據結構。在文章最後我也指出，單調棧的關鍵是 「單調性」，而不是 「棧」。我們學習單調棧和單端隊列，應該當作學習單調性的思想在棧或者隊列上的應用。

我們已經不是第一次討論 「單調性」 了，老讀者應該有印象，在討論二分查找時，我們曾經指出 「單調性是二分查找的必要條件」。舉個例子，對於一個單調遞增序列，當中位數小於目標數時，那我們可以確定：左半區間一定不是解，右半區間可能有解，問題規模直接縮小一半。最終整個二分查找演算法的時間複雜度從暴力查找 $O(n)$，降低到 $O(lgn)$。反之，如果數據並不是單調的，那麼跟中位數比較就沒有意義。

5.2 優先隊列與單調隊列對比

優先隊列也叫小頂堆或大頂堆，每從堆頂取一個數據，底層的二叉堆會自動進行堆排序，保持堆頂元素是整個堆的最值。所以，雖然整個堆不是單調的，但堆頂是動態單調的。優先隊列雖然也叫隊列，但它並不能維護元素的位置關係，出隊順序和入隊順序無關。

6. 總結

到這裡，單調隊列和單調棧的內容都講完了。和單調棧一樣，除了典型例題之外，大部分題目會將 「滑動窗口最大值素」 的語義隱藏在題目細節中，需要找出題目的抽象模型或轉換思路才能找到，這是難的地方。

還是那句話，學習單調隊列和單調棧，應該當作學習單調性的思想在這兩種數據結構上的應用。你覺得呢？

更多同類型題目：

參考資料

• LeetCode 專題 · 單調隊列 —— LeetCode 出品
• LeetCode 題解 · 239. 滑動窗口最大值 —— LeetCode 出品
• LeetCode 題解 · 239. 單調隊列解題詳解 —— labuladong 著