前言

大家好排嫌，我是小彭对粪。

在上一篇文章中芯勘，我們介紹了單調(diào)棧這種特殊的棧結(jié)構(gòu)箱靴，單調(diào)棧是一種非常適合處理 “下一個更大元素問題” 的數(shù)據(jù)結(jié)構(gòu)。今天荷愕，分享到單調(diào)棧的孿生兄弟 —— 單調(diào)隊列（Monotonic Queue）衡怀。類似地，單調(diào)隊列也是在隊列的基礎(chǔ)上增加了單調(diào)的性質(zhì)（單調(diào)遞增或單調(diào)遞減）路翻。那么單調(diào)隊列是用來解決什么問題的呢狈癞？

學(xué)習(xí)路線圖：

1. 單調(diào)隊列的典型問題

單調(diào)隊列是一種用來高效地解決 “滑動窗口最大值” 問題的數(shù)據(jù)結(jié)構(gòu)茄靠。

舉個例子茂契，給定一個整數(shù)數(shù)組，要求輸出數(shù)組中大小為 K 的窗口中的最大值慨绳，這就是窗口最大值問題掉冶。而如果窗口從最左側(cè)逐漸滑動到數(shù)組的最右端，要求輸出每次移動后的窗口最大值脐雪，這就是滑動窗口問題厌小。這個問題同時也是 LeetCode 上的一道典型例題：LeetCode · 239. 滑動窗口最大值

LeetCode 例題

這個問題的暴力解法很容易想到：就是每次移動后遍歷整個滑動窗口找到最大值，單次遍歷的時間復(fù)雜度是 战秋，整體的時間復(fù)雜度是 璧亚，空間復(fù)雜度是 。當然脂信，暴力解法里的重復(fù)比較運算也是很明顯的癣蟋，我們每次僅僅往窗口里增加一個元素，都需要與窗口中所有元素對比找到最大值狰闪。

那么疯搅，有沒有更高效的算法呢？

滑動窗口最大值問題

或許埋泵，我們可以使用一個變量來記錄上一個窗口中的最大值幔欧，每增加一個新元素，只需要與這個 “最大值” 比較即可丽声。

然而礁蔗，窗口大小是固定的，每加入一個新元素后雁社，也要剔除一個元素浴井。如果剔除的元素正好是變量記錄的最大值，那說明這個值已經(jīng)失效歧胁。我們還是需要花費 時間重新找出最大值滋饲。那還有更快的方法尋找最大值嗎厉碟？

2. 解題思路

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

在暴力解法中，我們每移動一次窗口都需要遍歷整個窗口中的所有元素找出 “滑動窗口的最大值”⊥犁裕現(xiàn)在我們不這么做箍鼓，我們把滑動窗口中的所有元素緩存到某種數(shù)據(jù)容器中，每次窗口滑動后也向容器增加一個新的元素呵曹，而容器的最大值就自然是滑動窗口的最大值款咖。

現(xiàn)在，我們的問題已經(jīng)發(fā)生轉(zhuǎn)變奄喂，問題變成了：“如何尋找數(shù)據(jù)容器中的最大值”铐殃。 另外，根據(jù)題目條件限制跨新，這個容器是帶有約束的：因為窗口大小是固定的富腊，所以每加入一個新元素后，必然也要剔除一個元素域帐。 我們的數(shù)據(jù)容器也要滿足這個約束赘被。 現(xiàn)在，我們把注意力集中在這個容器上肖揣，思考一下用什么數(shù)據(jù)結(jié)構(gòu)民假、用什么算法可以更高效地解決問題。由于這個容器是我們額外增加的龙优，所以我們有足夠的操作空間羊异。

先說結(jié)論：

• 方法 1 - 暴力： 遍歷整個數(shù)據(jù)容器中所有元素，單次操作的時間復(fù)雜度是 彤断，整體時間復(fù)雜度是 野舶；
• 方法 2 - 二叉堆： 不需要遍歷整個數(shù)據(jù)容器，可以用大頂堆維護容器的最大值瓦糟，單次操作的時間復(fù)雜度是 筒愚，整體時間復(fù)雜度是 ；
• 方法 3 - 雙端隊列： 我們發(fā)現(xiàn)二叉堆中很多中間元素是冗余的菩浙，拉低了效率巢掺。我們可以在每處理一個元素時，可以先觀察容器中剛剛加入的元素劲蜻，如果剛剛加入的元素小于當前元素陆淀，則直接將其丟棄（后進先出邏輯）。最先加入容器的元素先嬉，如果超出了滑動窗口的范圍轧苫，也直接將其丟棄（先進先出邏輯）。所以這個容器數(shù)據(jù)結(jié)構(gòu)要用雙端隊列實現(xiàn)。因為每個元素最多只會入隊和出隊一次含懊，所以整體的計算規(guī)模還是與數(shù)據(jù)規(guī)模成正比的身冬，整體時間復(fù)雜度是 。

下面岔乔，我們先從優(yōu)先隊列說起酥筝。

3. 優(yōu)先隊列解法

尋找最值的問題第一反應(yīng)要想到二叉堆。

我們可以維護一個大頂堆雏门，初始時先把第一個滑動窗口中的前 個元素放入大頂堆嘿歌。滑動窗口每移動一步茁影，就把一個新的元素放入大頂堆宙帝。大頂堆會自動進行堆排序，堆頂?shù)脑鼐褪钦麄€堆中 個元素的最值募闲。然而步脓，這個最大值可能是失效的（不在滑動窗口的范圍內(nèi)），我們要怎么處理這個約束呢蝇更？

我們可以用一個小技巧：將元素的下標放入隊列中沪编，用 nums[index] 比較元素大小，用 index 判斷元素有效性年扩。 此時，每次取堆頂元素時访圃，如果發(fā)現(xiàn)該元素的下標超出了窗口范圍厨幻，就直接丟棄。

題解

class Solution {
    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        // 結(jié)果數(shù)組
        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
    }
}

我們來分析優(yōu)先隊列解法的復(fù)雜度：

• 時間復(fù)雜度： 最壞情況下（遞增序列）腿时，所有元素都被添加到優(yōu)先隊列里况脆，優(yōu)先隊列的單次操作時間復(fù)雜度是 ，所以整體時間復(fù)雜度是 批糟；
• 空間復(fù)雜度： 使用了額外的優(yōu)先級隊列格了，所以整體的時間復(fù)雜度是 。

優(yōu)先隊列解法的時間復(fù)雜度從 變成 徽鼎，這個效果很難讓人滿意盛末，有更好的辦法嗎？

我們繼續(xù)分析發(fā)現(xiàn)否淤，由于滑動窗口是從左往右移動的悄但，所以當一個元素 的后面出現(xiàn)一個更大的元素 ，那么 就永遠不可能是滑動窗口的最大值了石抡，我們可以永久地將它剔除掉檐嚣。然而，在優(yōu)先隊列中啰扛，失去價值的 會一直存儲在隊列中嚎京，從而拉低了優(yōu)先隊列的效率嗡贺。

4. 單調(diào)隊列解法

我們可以維護一個數(shù)據(jù)容器，第一個元素先放到容器中鞍帝，后續(xù)每處理一個元素暑刃，先觀察容器中剛剛加入的元素，如果剛剛加入的元素小于當前元素膜眠，則直接將其丟棄（因為新增加的元素排在后面岩臣，會更晚地離開滑動窗口，所以中間的小元素永遠沒有資格了）宵膨，避免拉低效率架谎。

繼續(xù)分析我們還發(fā)現(xiàn)：

• 這個數(shù)據(jù)容器中后進入的元素需要先彈出與當前元素對比，符合 “后進先出” 邏輯辟躏，所以這個數(shù)據(jù)結(jié)構(gòu)要用棧谷扣；
• 這個數(shù)據(jù)容器中先進入的元素需要先彈出丟棄（離開滑動窗口），符合 “先進先出” 邏輯捎琐，所以這個數(shù)據(jù)結(jié)構(gòu)要用隊列会涎；

因此，這個數(shù)據(jù)結(jié)構(gòu)同時具備棧和隊列的特點瑞凑，是需要同時在兩端操作的雙端隊列末秃。這個問題也可以形象化地思考：把數(shù)字想象為有 “重量” 的的杠鈴片，滑動窗口每移動一次后籽御，新增加的大杠鈴片會把中間小的杠鈴片壓扁练慕，后續(xù)不再考慮它們。

形象化思考

Untitled 3.png

題解

class Solution {
    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        // 結(jié)果數(shù)組
        val result = IntArray(nums.size - k + 1) { -1 }
        // 單調(diào)隊列（基于雙端隊列）
        val queue = LinkedList<Int>()
        for (index in nums.indices) {
            // while：隊尾元素比當前元素小技掏，說明隊尾元素不再可能是最大值铃将，后續(xù)不再考慮它
            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
    }
}

單調(diào)隊列與單調(diào)棧的思路是非常類似的，單調(diào)棧在每次遍歷中哑梳，會將棧頂 “被壓扁的小杠鈴片” 彈出棧劲阎，而單調(diào)隊列在每次遍歷中，會將隊尾中 “被壓扁的小杠鈴片” 彈出隊鸠真。 單調(diào)棧在棧頂過濾無效元素悯仙，在棧頂獲取目標元素，單調(diào)隊列在隊尾過濾無效元素弧哎，在隊頭獲取目標元素雁比。

理解了單調(diào)隊列的解題模板后，我們來分析它的復(fù)雜度：

• 時間復(fù)雜度： 雖然代碼中有嵌套循環(huán)撤嫩，但它的時間復(fù)雜度并不是 偎捎，而是 。因為每個元素最多只會入棧和出棧一次，所以整體的計算規(guī)模還是與數(shù)據(jù)規(guī)模成正比的茴她，整體時間復(fù)雜度是 寻拂；
• 空間復(fù)雜度： 最壞情況下（遞增序列），所有元素被添加到隊列中丈牢，所以空間復(fù)雜度是 祭钉。

5. 單調(diào)棧、單調(diào)隊列己沛、優(yōu)先隊列對比

5.1 單調(diào)棧與單調(diào)隊列的選擇

單調(diào)隊列和單調(diào)棧在很大程度上是類似的慌核，它們均是在原有數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上增加的單調(diào)的性質(zhì)。那么申尼，什么時候使用單調(diào)棧垮卓，什么時候使用單調(diào)隊列呢？ 主要看你的算法中元素被排除的順序师幕，如果先進入集合的元素先排除粟按，那么使用棧（LIFO）；如果先進入集合的元素后排除霹粥，那么使用隊列（FIFO）灭将。 在例題中，甚至出現(xiàn)了同時結(jié)合棧和隊列的情況后控。

上一篇文章里我們討論過單調(diào)棧庙曙，單調(diào)棧是一種非常適合解決 ”下一個更大元素“ 的數(shù)據(jù)結(jié)構(gòu)。在文章最后我也指出忆蚀，單調(diào)棧的關(guān)鍵是 “單調(diào)性”矾利，而不是 “棧”馋袜。我們學(xué)習(xí)單調(diào)棧和單端隊列，應(yīng)該當作學(xué)習(xí)單調(diào)性的思想在棽案或者隊列上的應(yīng)用欣鳖。

我們已經(jīng)不是第一次討論 “單調(diào)性” 了，老讀者應(yīng)該有印象茴厉，在討論二分查找時泽台，我們曾經(jīng)指出 “單調(diào)性是二分查找的必要條件”。舉個例子矾缓，對于一個單調(diào)遞增序列怀酷，當中位數(shù)小于目標數(shù)時，那我們可以確定：左半?yún)^(qū)間一定不是解嗜闻，右半?yún)^(qū)間可能有解蜕依，問題規(guī)模直接縮小一半。最終整個二分查找算法的時間復(fù)雜度從暴力查找 ，降低到 样眠。反之友瘤，如果數(shù)據(jù)并不是單調(diào)的，那么跟中位數(shù)比較就沒有意義檐束。

5.2 優(yōu)先隊列與單調(diào)隊列對比

優(yōu)先隊列也叫小頂堆或大頂堆辫秧，每從堆頂取一個數(shù)據(jù)，底層的二叉堆會自動進行堆排序被丧，保持堆頂元素是整個堆的最值盟戏。所以，雖然整個堆不是單調(diào)的甥桂，但堆頂是動態(tài)單調(diào)的柿究。優(yōu)先隊列雖然也叫隊列，但它并不能維護元素的位置關(guān)系格嘁，出隊順序和入隊順序無關(guān)笛求。

6. 總結(jié)

到這里懂诗，單調(diào)隊列和單調(diào)棧的內(nèi)容都講完了蜂嗽。和單調(diào)棧一樣，除了典型例題之外殃恒，大部分題目會將 “滑動窗口最大值素” 的語義隱藏在題目細節(jié)中植旧，需要找出題目的抽象模型或轉(zhuǎn)換思路才能找到，這是難的地方离唐。

還是那句話病附，學(xué)習(xí)單調(diào)隊列和單調(diào)棧，應(yīng)該當作學(xué)習(xí)單調(diào)性的思想在這兩種數(shù)據(jù)結(jié)構(gòu)上的應(yīng)用亥鬓。你覺得呢完沪？

更多同類型題目：

參考資料

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