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

本文已收錄到 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 優先佇列與單調佇列對比

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

資料結構	特點	單調性 / 有序性
單調棧	後進先出（LIFO），出隊順序由入棧順序決定	靜態
單調佇列	先進先出（FIFO），出隊順序由入隊順序決定	靜態單調序列
優先佇列	出隊順序與入隊順序無關，而由優先順序順序決定	整個堆不是單調的，但堆頂是動態單調的

6. 總結

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

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

更多同型別題目：

單調佇列	難度	題解
239. 滑動視窗最大值	Hard	【題解】
918. 環形子陣列的最大和	Medium	【題解】
面試題59 - II. 佇列的最大值	Medium	【題解】

參考資料

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

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

前言