0x11 棧

棧是一種“先進后出”的線性數(shù)據(jù)結(jié)構(gòu)。棧只有一端能夠進出元素，我們一般稱這一端為棧頂，另一端為棧底。添加或刪除棧中元素時，我們只能將其插入到棧頂（進棧），或者把棧頂元素從棧頂取出（出棧）。

實現(xiàn)一個棧，支持查找棧中最小值的操作，要求時間復雜度為O(1)。

我們可以建立兩個棧，一個棧A記錄原本的數(shù)據(jù)，另一個棧B儲存棧A中以棧底開頭的的每段數(shù)據(jù)最小值，就像下面一樣：

A: 9 2 1 5 3 0 2 <—

B: 9 2 1 1 1 0 0 <—

1.表達式計算

棧的一大用途是做算術(shù)表達式的計算。算術(shù)表達式通常有前綴、中綴、后綴三種表達方式。

中綴表達式，我們最常見的表達式，例如：3 * ( 1 - 2 )。

前綴表達式，又稱波蘭式，形如“op A B”，其中op是一個運算符，A，B是另外兩個前綴表達式。例如：* 3 - 1 2。

后綴表達式，有又稱逆波蘭式，形如“A B op”，例如：1 2 - 3 *。

前綴和后綴表達式的值的定義是，先遞歸求出A，B的值，二者再做op運算的結(jié)果。這兩種表達式不需要使用括號，其運算方案是唯一確定的。對于計算機來說，它最容易理解后綴表達式，我們可以使用棧來$O(N)$地求出它的值。

后綴表達式求法

1.建立一個用于存數(shù)的棧，逐一掃描該后綴表達式中的元素。

（1）如果遇到一個數(shù)，則把該數(shù)入棧。

（2）如果遇到運算符，就取出棧頂?shù)膬蓚€數(shù)進行運算，然后把結(jié)果入棧。

2.掃描完成后，棧中恰好有一個元素，就是該后綴表達式的值。

如果想要計算機求解我們常用的中綴表達式的值，最快的方式就是把中綴表達式轉(zhuǎn)化成后綴表達式，再使用上述方法求值。這個轉(zhuǎn)化過程同樣可以使用棧來$O(n)$完成。

中綴表達式轉(zhuǎn)化成后綴表達式

1.建立一個用于存運算符的棧，逐一掃描該中綴表達式中的值。

（1）如果遇到一個數(shù)，輸出該數(shù)。

（2）如果遇到左括號，把左括號入棧。

（3）如果遇到右括號，不斷取出棧頂并輸出，直到棧頂為左括號，然后把左括號出棧。

（4）如果遇到運算符，只要棧頂符號的優(yōu)先級大于等于新符號，就不斷取出棧頂并輸出，最后把新符號入棧。優(yōu)先級為乘除>加減>左括號。

2.依次取出并輸出棧中所有的剩余符號，最終輸出的序列就是與原中綴表達式等價的后綴表達式。

當然我們也可以不轉(zhuǎn)化成后綴表達式，而是使用遞歸法直接求解中綴表達式的值，其時間復雜度為$O(N^2)$。

中綴表達式的遞歸求法

目標：求解中綴表達式S[1~N]的值

子問題：求解中綴表達式S的子區(qū)間表達式S[L~R]的值。

1.在L~R中考慮沒有被任何括號包含的運算符：

（1）若存在加減號，選其中最后一個，分成左右兩半遞歸，結(jié)果相加減，返回。

（2）若存在乘除號，選其中最后一個，分成左右兩半遞歸，結(jié)果相乘除，返回。

2.若不存在沒有被任何括號包含的運算符：

（1）若首尾字符是括號，遞歸求解S[L+1~R-1]，把結(jié)果返回。

（2）否則，說明區(qū)間S[L~R]是一個數(shù)，直接返回。

2.單調(diào)棧

如下圖所示，在一個水平上方有若干個矩形，求包含與這些矩形的并集內(nèi)部的最大矩形的面積（在下圖中，答案就是陰影部分的面積），矩形個數(shù)$\le 10^5$。

如果矩形的高度從左往右遞增，我們可以嘗試每個矩形的高度作為最終矩形的高度，并把寬度延伸到右邊界，得到一個矩形，在所有這樣的矩形中取面積的最大值就是答案。如下圖所示：

如果下一個矩形的高度小于上一個矩形的高度，那么該矩形想利用之前的矩形一起構(gòu)成一塊較大的面積時，這塊面積的高度就不可能超過該矩形自身的高度。換句話說，在考慮完上圖的四種情況后，下圖中打叉的那部分面積就沒有任何用處了。

既然沒有用，就把這些比該矩形高的矩形都刪掉，用一個寬度累加、高度為該矩形自身高度的新矩形（就是上圖的陰影部分）來代替。這樣不會對后續(xù)的計算產(chǎn)生任何影響。于是我們維護的輪廓就變成了一個高度始終單調(diào)遞增的矩形序列。

詳細來說，我們建立一個棧，用來保存若干個矩形，這些矩形的高度是單調(diào)遞增的，我們從左往右依次掃描每個矩形：

如果矩形比當前棧頂矩形高，直接入棧。

否則不斷取出棧頂，直到棧為空或者棧頂矩形的高度比當前矩形小。在出棧過程中，我們累計被彈出的矩形寬度之和，并且每彈出一個矩形，就用它的高度乘上累計的寬度去更新答案。整個出棧過程結(jié)束，我們把一個高度為當前高度、寬度為累計寬度的新矩形入棧。

整個掃描結(jié)束，我們把棧中的剩余矩形依次彈出，按照與上面相同的方法更新答案。為了簡化程序我們也可以增加一個高度為0的矩形a[n+1],以避免在掃描結(jié)束后棧中有剩余矩形。

long long ans=0;
int p=0;
a[n+1]=s[p]=0;
for(int i=1;i<=n+1;++i)
{
    if(a[i]>=s[p])
        s[++p]=a[i],w[p]=1;
    else
    {
        int width=0;
        while(s[p]>a[i])
        {
            width+=w[p];
            ans=max(ans,(long long)width*s[p]);
            --p;
        }
        s[++p]=a[i],w[p]=width+1;
    }
}

這就是著名的單調(diào)棧算法，時間復雜度為$O(n)$。借助單調(diào)性處理問題的思想在于及時排除不可能的選項，保持策略集合的高度有效性和秩序性，從而為我們做出決策提供更多的條件和可能方法。

實際應用：尋找到數(shù)組中一個數(shù)上一個或下一個更大數(shù)或更小數(shù)的位置。一個序列通過單調(diào)棧，我們可以找到序列中數(shù)A前面小于它的第一個數(shù)B。改成遞減排列，也可以找到序列中數(shù)A前面大于它的第一個數(shù)B。也可以通過反向輸入序列，找到序列中數(shù)A后面大于或小于它的第一個數(shù)B。文章來源地址http://www.zghlxwxcb.cn/news/detail-758931.html

到了這里，關(guān)于0x11 棧的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！