使用單調隊列解決 “滑動視窗最大值” 問題

1\. 單調隊列的典型問題

單調隊列是一種用來高效地解決 “滑動視窗最大值” 問題的資料結構。

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

​

​LeetCode 例題​

​

這個問題的暴力解法很容易想到：就是每次移動後周遊整個滑動視窗找到最大值，單次周遊的時間複雜度是

，整體的時間複雜度是

，空間複雜度是

。當然，暴力解法裡的重複比較運算也是很明顯的，我們每次僅僅往視窗裡增加一個元素，都需要與視窗中所有元素對比找到最大值。

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

​

​滑動視窗最大值問題​

​

或許，我們可以使用一個變量來記錄上一個視窗中的最大值，每增加一個新元素，隻需要與這個 “最大值” 比較即可。

然而，視窗大小是固定的，每加入一個新元素後，也要剔除一個元素。如果剔除的元素正好是變量記錄的最大值，那說明這個值已經失效。我們還是需要花費

時間重新找出最大值。那還有更快的方法尋找最大值嗎？

2\. 解題思路

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

在暴力解法中，我們每移動一次視窗都需要周遊整個視窗中的所有元素找出 “滑動視窗的最大值”。現在我們不這麼做，我們把滑動視窗中的所有元素緩存到某種資料容器中，每次視窗滑動後也向容器增加一個新的元素，而容器的最大值就自然是滑動視窗的最大值。

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

先說結論：

• 方法 1 - 暴力： 周遊整個資料容器中所有元素，單次操作的時間複雜度是
• ，整體時間複雜度是
• ；
• 方法 2 - 二叉堆： 不需要周遊整個資料容器，可以用大頂堆維護容器的最大值，單次操作的時間複雜度是
• ，整體時間複雜度是
• ；
• 方法 3 - 雙端隊列： 我們發現二叉堆中很多中間元素是備援的，拉低了效率。我們可以在每處理一個元素時，可以先觀察容器中剛剛加入的元素，如果剛剛加入的元素小于目前元素，則直接将其丢棄（後進先出邏輯）。最先加入容器的元素，如果超出了滑動視窗的範圍，也直接将其丢棄（先進先出邏輯）。是以這個容器資料結構要用雙端隊列實作。因為每個元素最多隻會入隊和出隊一次，是以整體的計算規模還是與資料規模成正比的，整體時間複雜度是
• 。

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

3\. 優先隊列解法

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

我們可以維護一個大頂堆，初始時先把第一個滑動視窗中的前

個元素放入大頂堆。滑動視窗每移動一步，就把一個新的元素放入大頂堆。大頂堆會自動進行堆排序，堆頂的元素就是整個堆中

個元素的最值。然而，這個最大值可能是失效的（不在滑動視窗的範圍内），我們要怎麼處理這個限制呢？

我們可以用一個小技巧：将元素的下标放入隊列中，用 ​

​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
    }
}      

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

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

優先隊列解法的時間複雜度從

變成

，這個效果很難讓人滿意，有更好的辦法嗎？

我們繼續分析發現，由于滑動視窗是從左往右移動的，是以當一個元素

的後面出現一個更大的元素

，那麼

就永遠不可能是滑動視窗的最大值了，我們可以永久地将它剔除掉。然而，在優先隊列中，失去價值的

會一直存儲在隊列中，進而拉低了優先隊列的效率。

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
    }
}      

單調隊列與單調棧的思路是非常類似的，單調棧在每次周遊中，會将棧頂 “被壓扁的小杠鈴片” 彈出棧，而單調隊列在每次周遊中，會将隊尾中 “被壓扁的小杠鈴片” 彈出隊。 單調棧在棧頂過濾無效元素，在棧頂擷取目标元素，單調隊列在隊尾過濾無效元素，在隊頭擷取目标元素。

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

• 時間複雜度： 雖然代碼中有嵌套循環，但它的時間複雜度并不是
• ，而是
• 。因為每個元素最多隻會入棧和出棧一次，是以整體的計算規模還是與資料規模成正比的，整體時間複雜度是
• ；
• 空間複雜度： 最壞情況下（遞增序列），所有元素被添加到隊列中，是以空間複雜度是
• 。

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

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

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

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

我們已經不是第一次讨論 “單調性” 了，老讀者應該有印象，在讨論二分查找時，我們曾經指出 “單調性是二分查找的必要條件”。舉個例子，對于一個單調遞增序列，當中位數小于目标數時，那我們可以确定：左半區間一定不是解，右半區間可能有解，問題規模直接縮小一半。最終整個二分查找算法的時間複雜度從暴力查找

，降低到

。反之，如果資料并不是單調的，那麼跟中位數比較就沒有意義。

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

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

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

6\. 總結

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

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

更多同類型題目：

單調隊列	難度	題解
​​239\. 滑動視窗最大值​​	Hard	​​【題解】​​
​​918\. 環形子數組的最大和​​	Medium	​​【題解】​​