LeetCode Monotone Stack Summary 單調(diào)棧小結(jié)

所謂的單調(diào)棧 Monotone Stack，就是棧內(nèi)元素都是單調(diào)遞增或者單調(diào)遞減的，有時(shí)候需要嚴(yán)格的單調(diào)遞增或遞減，根據(jù)題目的具體情況來看吧。關(guān)于單調(diào)棧，這個(gè)帖子講的不錯(cuò)，而且舉了個(gè)排隊(duì)的例子來類比。那么，博主也舉個(gè)生動(dòng)的例子來說明吧：比如有一天，某家店在發(fā) free food，很多人在排隊(duì)，于是你也趕過去湊熱鬧。但是由于來晚了，隊(duì)伍已經(jīng)很長了，想著不然就插個(gè)隊(duì)啥的。但發(fā)現(xiàn)排在隊(duì)伍最前面的都是一些有紋身的大佬，惹不起，只能贊美道，小豬佩奇身上紋，來世還做社會(huì)人。于是往隊(duì)伍后面走，發(fā)現(xiàn)是一群小屁孩，直接全部攆走，然后排在了社會(huì)大佬們的后面。那么這就是一個(gè)單調(diào)遞減的棧，按實(shí)力遞減。由于棧元素是后進(jìn)先出的，所以上面的例子正確的檢查順序應(yīng)該是從隊(duì)尾往前遍歷，小屁孩都攆走，直到遇到大佬停止，然后排在大佬后面（假設(shè)這個(gè)隊(duì)列已經(jīng)事先按實(shí)力遞減排好了）。

明白了單調(diào)棧的加入元素的過程后，我們來看看它的性質(zhì)，以及為啥要用單調(diào)棧。單調(diào)棧的一大優(yōu)勢就是線性的時(shí)間復(fù)雜度，所有的元素只會(huì)進(jìn)棧一次，而且一旦出棧后就不會(huì)再進(jìn)來了。

單調(diào)遞增?？梢哉业阶笃鸬谝粋€(gè)比當(dāng)前數(shù)字小的元素。比如數(shù)組 [2 1 4 6 5]，剛開始2入棧，數(shù)字1入棧的時(shí)候，發(fā)現(xiàn)棧頂元素2比較大，將2移出棧，此時(shí)1入棧。那么2和1都沒左起比自身小的數(shù)字。然后數(shù)字4入棧的時(shí)候，棧頂元素1小于4，于是1就是4左起第一個(gè)小的數(shù)字。此時(shí)棧里有1和4，然后數(shù)字6入棧的時(shí)候，棧頂元素4小于6，于是4就是6左起第一個(gè)小的數(shù)字。此時(shí)棧里有1，4，6，然后數(shù)字5入棧的時(shí)候，棧頂元素6大于5，將6移除，此時(shí)新的棧頂元素4小于5，那么4就是5左起的第一個(gè)小的數(shù)字，最終棧內(nèi)數(shù)字為 1，4，5。

單調(diào)遞減?？梢哉业阶笃鸬谝粋€(gè)比當(dāng)前數(shù)字大的元素。這里就不舉例說明了，同樣的道理，大家可以自行驗(yàn)證一下。

性質(zhì)搞懂了后，下面來看一下應(yīng)用，什么樣的場景下適合使用單調(diào)棧呢？可以看下 Max Chunks To Make Sorted II 這篇帖子的解法四，但這道題并不是單調(diào)棧的最典型應(yīng)用，只能說能想到用單調(diào)棧確實(shí)牛b，但一般情況下是不容易想到的。我們來看一些特別適合用單調(diào)棧來做的題目吧。

首推 Trapping Rain Water 這道題，雖然博主開始也沒有注意到可以使用單調(diào)棧來做。但實(shí)際上是一道相當(dāng)合適的題，來復(fù)習(xí)一下題目：

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

給了邊界的高度（黑色部分），讓求能裝的水量（藍(lán)色部分）。 為啥能用單調(diào)棧來做呢？我們先來考慮一下，什么情況下可以裝下水呢，是不是必須兩邊高，中間低呢？我們對低洼的地方感興趣，就可以使用一個(gè)單調(diào)遞減棧，將遞減的邊界存進(jìn)去，一旦發(fā)現(xiàn)當(dāng)前的數(shù)字大于棧頂元素了，那么就有可能會(huì)有能裝水的地方產(chǎn)生。此時(shí)我們當(dāng)前的數(shù)字是右邊界，我們從棧中至少需要有兩個(gè)數(shù)字，才能形成一個(gè)坑槽，先取出的那個(gè)最小的數(shù)字，就是坑槽的最低點(diǎn)，再次取出的數(shù)字就是左邊界，我們比較左右邊界，取其中較小的值為裝水的邊界，然后此高度減去水槽最低點(diǎn)的高度，乘以左右邊界間的距離就是裝水量了。由于需要知道左右邊界的位置，所以我們雖然維護(hù)的是遞減棧，但是棧中數(shù)字并不是存遞減的高度，而是遞減的高度的坐標(biāo)。這應(yīng)該屬于單調(diào)棧的高級(jí)應(yīng)用了，可能并不是那么直接就能想出正確的解法。

再來看一道 Largest Rectangle in Histogram，這道求直方圖中的最大矩陣的題，也是非常適合用單調(diào)棧來做的，來復(fù)習(xí)一下題目：

For example,
Given height = [2,1,5,6,2,3],
return 10.

我們可以看到，直方圖矩形面積要最大的話，需要盡可能的使得連續(xù)的矩形多，并且最低一塊的高度要高。有點(diǎn)像木桶原理一樣，總是最低的那塊板子決定桶的裝水量。那么既然需要用單調(diào)棧來做，首先要考慮到底用遞增棧，還是用遞減棧來做。我們想啊，遞增棧是維護(hù)遞增的順序，當(dāng)遇到小于棧頂元素的數(shù)就開始處理，而遞減棧正好相反，維護(hù)遞減的順序，當(dāng)遇到大于棧頂元素的數(shù)開始處理。那么根據(jù)這道題的特點(diǎn)，我們需要按從高板子到低板子的順序處理，先處理最高的板子，寬度為1，然后再處理旁邊矮一些的板子，此時(shí)長度為2，因?yàn)橹暗母甙遄涌山M成矮板子的矩形 ，因此我們需要一個(gè)遞增棧，當(dāng)遇到大的數(shù)字直接進(jìn)棧，而當(dāng)遇到小于棧頂元素的數(shù)字時(shí)，就要取出棧頂元素進(jìn)行處理了，那取出的順序就是從高板子到矮板子了，于是乎遇到的較小的數(shù)字只是一個(gè)觸發(fā)，表示現(xiàn)在需要開始計(jì)算矩形面積了，為了使得最后一塊板子也被處理，這里用了個(gè)小trick，在高度數(shù)組最后面加上一個(gè)0，這樣原先的最后一個(gè)板子也可以被處理了。由于棧頂元素是矩形的高度，那么關(guān)鍵就是求出來寬度，那么跟之前那道 Trapping Rain Water 一樣，單調(diào)棧中不能放高度，而是需要放坐標(biāo)。由于我們先取出棧中最高的板子，那么就可以先算出長度為1的矩形面積了，然后再取下一個(gè)板子，此時(shí)根據(jù)矮板子的高度算長度為2的矩形面積，以此類推，直到數(shù)字大于棧頂元素為止，再次進(jìn)棧，巧妙的一比！

初步來總結(jié)一下單調(diào)棧吧，單調(diào)棧其實(shí)是一個(gè)看似原理簡單，但是可以變得很難的解法。線性的時(shí)間復(fù)雜度是其最大的優(yōu)勢，每個(gè)數(shù)字只進(jìn)棧并處理一次，而解決問題的核心就在處理這塊，當(dāng)前數(shù)字如果破壞了單調(diào)性，就會(huì)觸發(fā)處理?xiàng)ｍ斣氐牟僮鳎|發(fā)數(shù)字有時(shí)候是解決問題的一部分，比如在 Trapping Rain Water 中作為右邊界。有時(shí)候僅僅觸發(fā)作用，比如在 Largest Rectangle in Histogram 中是為了開始處理?xiàng)ｍ斣?，如果僅作為觸發(fā)，可能還需要在數(shù)組末尾增加了一個(gè)專門用于觸發(fā)的數(shù)字。另外需要注意的是，雖然是遞增或遞減棧，但里面實(shí)際存的數(shù)字并不一定是遞增或遞減的，因?yàn)槲覀兛梢源孀鴺?biāo)，而這些坐標(biāo)帶入數(shù)組中才會(huì)得到遞增或遞減的數(shù)。所以對于玩數(shù)組的題，如果相互之間關(guān)聯(lián)很大，那么就可以考慮考慮單調(diào)棧能否解題。

到此這篇關(guān)于LeetCode 單調(diào)棧內(nèi)容小結(jié)的文章就介紹到這了,更多相關(guān)LeetCode 單調(diào)棧內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論