點(diǎn)贊關(guān)注溶浴，不再迷路，你的支持對(duì)我意義重大管引！

?? Hi士败，我是丑丑。本文「數(shù)據(jù)結(jié)構(gòu) & 算法」| 導(dǎo)讀 —— 登高博見(jiàn) 已收錄褥伴，這里有 Android 進(jìn)階成長(zhǎng)路線筆記 & 博客谅将，歡迎跟著彭丑丑一起成長(zhǎng)。（聯(lián)系方式在 GitHub）

歷史上的今天

1938 年 3 月重慢，香農(nóng)發(fā)表時(shí)代論文饥臂。
這就是《繼電器和開(kāi)關(guān)電路的符號(hào)分析》("A Symbolic Analysis of Relay and Switching Circuits")。香農(nóng)在這篇論文中展示了如何把布爾代數(shù)的各種運(yùn)算應(yīng)用在開(kāi)關(guān)電路中似踱，將布爾代數(shù)中的 “真” “假” 和電路系統(tǒng)中的 “開(kāi)” “關(guān)” 對(duì)應(yīng)起來(lái)隅熙，并用 1 和 0 來(lái)標(biāo)示稽煤。這篇論文是開(kāi)關(guān)與邏輯電路理論和設(shè)計(jì)的開(kāi)山之作，也是所有數(shù)字計(jì)算機(jī)運(yùn)行的基礎(chǔ)猛们。 —— 《了不起的程序員》

前言

• 單調(diào)棧是一種非常適合處理 下一個(gè)更大元素（Next Greater Number ） 問(wèn)題的數(shù)據(jù)結(jié)構(gòu)念脯，在面試中比較冷門，建議應(yīng)試者合理安排學(xué)習(xí)時(shí)間弯淘；
• 在這篇文章里绿店，我將梳理單調(diào)棧的基本知識(shí) & 常考題型庐橙。如果能幫上忙假勿，請(qǐng)務(wù)必點(diǎn)贊加關(guān)注，這真的對(duì)我非常重要态鳖。

目錄

1. 單調(diào)椬啵基礎(chǔ)

1.1 定義

棧（Stack）是一種滿足后進(jìn)先出（LIFO）邏輯的數(shù)據(jù)結(jié)構(gòu)，大家都很熟悉了浆竭，單調(diào)棧實(shí)際上就是在棧的基礎(chǔ)上增加單調(diào)的性質(zhì)浸须。

比如有序就是最耳熟能詳?shù)膯握{(diào)性，每次新元素入棧時(shí)邦泄，我們可以采用一些額外的邏輯保證棧內(nèi)元素都是有序的删窒，這樣我們就得到了一個(gè)單調(diào)棧。出棧的時(shí)候不需要增加額外的邏輯顺囊，因?yàn)閷?duì)于一個(gè)單調(diào)棧（或者下篇文章提到的單調(diào)隊(duì)列）肌索，移除首尾的元素后剩下的元素肯定還是滿足單調(diào)性的。

單調(diào)性

單調(diào)性（monotonicity）也可以叫做增減性特碳，可以定性地描述兩個(gè)變量之間的關(guān)系诚亚。當(dāng)變量在其定義區(qū)間內(nèi)增大時(shí)，函數(shù)隨著增大（或減形缗摇）站宗，則稱函數(shù) y 在該區(qū)間單調(diào)遞增（或單調(diào)遞減）。

1.2 作用

理解了單調(diào)棧的定義硅瞧，下一個(gè)問(wèn)題就是單調(diào)棧有什么用份乒？

老讀者應(yīng)該有印象，我們不是第一次討論單調(diào)性了腕唧。我們?cè)?《算法 | 下次面試遇到二分查找或辖，別再寫錯(cuò)了》 就已經(jīng)提過(guò)單調(diào)性。還記得嗎枣接，我們說(shuō)單調(diào)性是二分查找的必要條件颂暇。

為什么單調(diào)性是二分查找必要條件呢？因?yàn)樵诙植檎依锏蹋覀冃枰獙?duì)比目標(biāo)數(shù)與數(shù)組的中位數(shù)耳鸯，來(lái)確定目標(biāo)數(shù)是落在左半?yún)^(qū)間湿蛔，還是右半?yún)^(qū)間。舉個(gè)例子县爬，對(duì)于一個(gè)單調(diào)遞增序列阳啥，當(dāng)中位數(shù)小于目標(biāo)數(shù)時(shí)，那我們可以確定：左半?yún)^(qū)間一定不是解财喳，右半?yún)^(qū)間可能有解察迟。

此時(shí)，問(wèn)題規(guī)模減少了一半（減治）耳高，整個(gè)二分查找算法的時(shí)間復(fù)雜度從暴力查找 扎瓶，降低到，這里面單調(diào)性功不可沒(méi)泌枪。

回到主題概荷，單調(diào)棧里的單調(diào)性有什么用？棧里雖然沒(méi)有中位數(shù)的概念碌燕，但是有棧頂?shù)母拍钗笾ぁＮ覀兛梢岳脳ｍ攣?lái)判斷棧內(nèi)其他元素是否存在解。 舉個(gè)例子修壕，對(duì)于一個(gè)從棧底到棧頂單調(diào)遞增的棧雷厂，當(dāng)棧頂元素小于目標(biāo)數(shù)，那么我們可以確定：棧內(nèi)元素都是小于目標(biāo)數(shù)的叠殷；而當(dāng)棧頂元素大于目標(biāo)數(shù)，那么只有棧頂前面一部分元素大于目標(biāo)數(shù)诈皿。

小結(jié)：利用了單調(diào)的特性林束，以空間換時(shí)間優(yōu)化時(shí)間復(fù)雜度。

1.3 局限性

相比于其他數(shù)據(jù)結(jié)構(gòu)稽亏，單調(diào)棧并不能覆蓋太大的問(wèn)題域壶冒，所以這種數(shù)據(jù)結(jié)構(gòu)的應(yīng)用價(jià)值就打折扣了。也只有 下一個(gè)更大元素（Next Greater Number ） 這一類問(wèn)題截歉，精準(zhǔn)命中單調(diào)棧的射程范圍胖腾。在 第 3 節(jié) 中，我整理了大量典型例題瘪松，應(yīng)該能覆蓋常見(jiàn)的題型咸作，多去看看加深理解。

2. 單調(diào)棧解題框架

前面的內(nèi)容相信大家很快就能理解了宵睦，我們直接看單調(diào)棧的原始題目 739. 每日溫度（Medium）记罚，并根據(jù)這個(gè)例子來(lái)討論單調(diào)棧的解題框架。

請(qǐng)根據(jù)每日氣溫列表壳嚎，重新生成一個(gè)列表桐智。對(duì)應(yīng)位置的輸出為：要想觀測(cè)到更高的氣溫末早，至少需要等待的天數(shù)。如果氣溫在這之后都不會(huì)升高说庭，請(qǐng)?jiān)谠撐恢糜?0 來(lái)代替然磷。

例如，給定一個(gè)列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]刊驴，你的輸出應(yīng)該是 [1, 1, 4, 2, 1, 1, 0, 0]姿搜。

提示：氣溫 列表長(zhǎng)度的范圍是 [1, 30000]。每個(gè)氣溫的值的均為華氏度缺脉，都是在 [30, 100] 范圍內(nèi)的整數(shù)痪欲。

這個(gè)問(wèn)題的暴力解法很容易想到：對(duì)每個(gè)元素掃描后續(xù)的每個(gè)元素，找到第一個(gè)更大的元素攻礼，整體時(shí)間復(fù)雜度是业踢，空間復(fù)雜度是。

下面我們來(lái)討論單調(diào)棧的解法：

• 1礁扮、從左到右遍歷每個(gè)元素知举，維護(hù)一個(gè)單調(diào)遞增棧，棧中存儲(chǔ)的是 「未確定解的元素下標(biāo)」太伊，下標(biāo)對(duì)應(yīng)的每日溫度遞增雇锡；
• 2、當(dāng)棧為空僚焦，將當(dāng)前元素下標(biāo)入棧锰提；
• 3.1 當(dāng)棧不為空，如果當(dāng)前元素大于等于棧頂元素芳悲，那么循環(huán)彈出棧頂元素立肘，直到棧為空或者當(dāng)前元素小于棧頂元素；
• 3.2 當(dāng)棧不為空名扛，如果當(dāng)前元素小于棧頂元素谅年，說(shuō)明當(dāng)前元素小于棧內(nèi)所有元素（單調(diào)性），將當(dāng)前元素入棧肮韧；
• 4融蹂、元素出棧時(shí)，計(jì)算下標(biāo)的差值就是間隔天數(shù)弄企。

—— 圖片引用自 LeetCode

這個(gè)問(wèn)題的題解基本上就是單調(diào)棧的解題框架：

fun dailyTemperatures(T: IntArray): IntArray {
    val result = IntArray(T.size) { 0 }

    1超燃、維護(hù)單調(diào)遞增棧
    val stack = ArrayDeque<Int>()

    for (index in T.indices) {
        while (!stack.isEmpty() && T[stack.peek()] < T[index]) {
            2、彈出棧頂小于等于目標(biāo)數(shù)的元素
            val preIndex = stack.pop() // 下標(biāo)出棧
            result[preIndex] = index - preIndex
        }
        3桩蓉、棧頂元素大于目標(biāo)數(shù)淋纲，那么棧內(nèi)所有元素都大于目標(biāo)數(shù)（單調(diào)性）
        stack.push(index) // 下標(biāo)入棧
    }
    return result
}

提示： 你可以看下官方題解的視頻講解加深理解：【官方題解】

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：
• 空間復(fù)雜度：

雖然代碼中有兩層循環(huán)，但是算法的時(shí)間復(fù)雜度并不是院究，這是因?yàn)閮?nèi)層循環(huán)并不是搜索整個(gè)數(shù)組（在暴力解法中洽瞬，內(nèi)層循環(huán)才是搜索整個(gè)數(shù)組）本涕。事實(shí)上，對(duì)于每個(gè)元素伙窃，它最多會(huì)入棧和出棧一次菩颖，不會(huì)因?yàn)閿?shù)據(jù)規(guī)模增大而導(dǎo)致每個(gè)元素增加額外的操作，所以每次操作的時(shí)間復(fù)雜度是为障。

3. 舉一反三

42. 接雨水（Hard） 【題解】

84. 柱狀圖中最大的矩形（Hard）

402. 移掉K位數(shù)字（Medium）

496. 下一個(gè)更大元素 I（Easy） 【題解】

503. 下一個(gè)更大元素 II（Medium）

739. 每日溫度（Medium） 【題解】

901. 股票價(jià)格跨度（Medium）

4. 總結(jié)

• 1晦闰、單調(diào)棧是在棧的基礎(chǔ)上，利用了單調(diào)的特性鳍怨，以空間換時(shí)間優(yōu)化時(shí)間復(fù)雜度呻右；
• 2、當(dāng)遇到下一個(gè)更大元素（Next Greater Number ）問(wèn)題時(shí)鞋喇，可以考慮使用單調(diào)棧處理声滥；
• 3、單調(diào)棧不能覆蓋太大的問(wèn)題域侦香，應(yīng)用價(jià)值不及其他數(shù)據(jù)結(jié)構(gòu)落塑。
• 4、單調(diào)棧還有一個(gè)孿生兄弟罐韩，你知道是什么嗎憾赁？

參考資料

• 《第 9 章 · 單調(diào)棧》 —— liweiwei1419 著
• 《單調(diào)棧解決 Next Greater Number 一類問(wèn)題》 —— labuladong 著
• 《每日溫度 · 官方題解》 —— LeetCode

創(chuàng)作不易散吵，你的「三連」是丑丑最大的動(dòng)力龙考，我們下次見(jiàn)！