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

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

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

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

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

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

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

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

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

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

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

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

初步來總結(jié)一下單調(diào)棧吧，單調(diào)棧其實是一個看似原理簡單，但是可以變得很難的解法。線性的時間復(fù)雜度是其最大的優(yōu)勢，每個數(shù)字只進棧并處理一次，而解決問題的核心就在處理這塊，當(dāng)前數(shù)字如果破壞了單調(diào)性，就會觸發(fā)處理棧頂元素的操作，而觸發(fā)數(shù)字有時候是解決問題的一部分，比如在 Trapping Rain Water 中作為右邊界。有時候僅僅觸發(fā)作用，比如在 Largest Rectangle in Histogram 中是為了開始處理棧頂元素，如果僅作為觸發(fā)，可能還需要在數(shù)組末尾增加了一個專門用于觸發(fā)的數(shù)字。另外需要注意的是，雖然是遞增或遞減棧，但里面實際存的數(shù)字并不一定是遞增或遞減的，因為我們可以存坐標(biāo)，而這些坐標(biāo)帶入數(shù)組中才會得到遞增或遞減的數(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)文章希望大家以后多多支持腳本之家！

最新評論