單調棧

What

單調棧也是棧的一種，滿足先進后出的原則，另外，單調棧中的元素是有序的，分為兩種

• 單調遞增棧：單調遞增棧就是從棧底到棧頂數據是從大到小

• 單調遞減棧：單調遞減棧就是從棧底到棧頂數據是從小到大

現在有一組數10，3，7，4，12。從左到右依次入棧，則如果棧為空或入棧元素值小于棧頂元素值，則入棧；否則，如果入棧則會破壞棧的單調性，則需要把比入棧元素小的元素全部出棧。單調遞減的棧反之。

• 10入棧時，棧為空，直接入棧，棧內元素為10。

• 3入棧時，棧頂元素10比3大，則入棧，棧內元素為10，3。

• 7入棧時，棧頂元素3比7小，則棧頂元素出棧，此時棧頂元素為10，比7大，則7入棧，棧內元素為10，7。

• 4入棧時，棧頂元素7比4大，則入棧，棧內元素為10，7，4。

• 12入棧時，棧頂元素4比12小，4出棧，此時棧頂元素為7，仍比12小，棧頂元素7繼續(xù)出棧，此時棧頂元素為10，仍比12小，10出棧，此時棧為空，12入棧，棧內元素為12。

Why

單調棧在解決一些問題時，比暴力循環(huán)方法要簡單的多，比如遇到，求一個數組在滿足元素比較條件下的統(tǒng)計數據時，可以考慮使用單調棧的做法，典型的就是后面第一次出現大于或者小于當前元素，要計算什么什么的時候。

How

適用單調棧的幾個條件：

• 求一個數組在滿足元素比較條件下的統(tǒng)計數據，比如求和，求面積等

• 由比較條件推出的單調棧的類型，然后棧中新添加的元素不符合時，可以對當前及其前向元素進行單獨統(tǒng)計后出棧，且不影響后續(xù)元素統(tǒng)計。

偽代碼如下：

// 此處一般需要給數組最后添加結束標志符，來滿足全部出棧
for (遍歷這個數組)
{
    if (棧空 || 棧頂元素大于等于當前比較元素)
    {
        入棧;
    } else {
        while (棧不為空 && 棧頂元素小于當前元素) {
            棧頂元素出棧;
            更新結果;
        }
        當前數據入棧;
    }
}
// 如果沒有結束標志符，此處要一般要單獨判斷全部出棧

Example

視野總和

先上題目和代碼

/*
描敘：有n個人站隊，所有的人全部向右看，個子高的可以看到個子低的發(fā)型，給出每個人的身高，問所有人能看到其他人發(fā)現總和是多少。
輸入：4 3 7 1
輸出：2
解釋：個子為4的可以看到個子為3的發(fā)型，個子為7可以看到個子為1的身高，所以1+1=2
*/
#define STACK_NUM_MAX 500

int VisionSumGet(int *arr, int arrSize)
{
    int stack[STACK_NUM_MAX] = {0}; /* 記錄元素位置的單調棧 */
    int top = -1; /* 此單調棧棧頂的索引, 初始位為-1, 棧為空*/
    int sum = 0;

    for (int i = 0; i < arrSize; i++) { /* 遍歷數組 */
        while ((top >= 0) && (arr[i] >= arr[stack[top]])) { /* 棧不為空, 且遇到數組元素相等或者大于棧頂對應的數組元素, 則看不到了，進行統(tǒng)計 */
            sum += (i - stack[top] - 1); /* 統(tǒng)計棧頂對應的數組元素看到的人數，并累加*/
            top--; /* 棧頂元素出，判斷下一個棧頂元素是否該統(tǒng)計累加 */
        }
        
        top++; /* 把當前的數組元素索引入棧 */
        stack[top] = i;
    }

    /* 最后還要進行一次計算 */
    while (top >= 0) {
        sum += (arrSize - stack[top] - 1);
        top--;
    }

    return sum;
}

首先，套一下單調棧的適用條件

• 這是一個數組，數組里的元素均向自己看，能看到的是比自己小的，不能看到的是比自己大的或者相等的，而且是要求每個元素能看到的所有元素的個數，顯然滿足第一個條件。
• 一個元素右邊能看到的是比自己小的，如果右邊有個比自己大的或者相等的，那么是不是可以統(tǒng)計此元素的情況，統(tǒng)計后，把此元素排除，是不是不會影響其右邊元素。因為統(tǒng)計數據與該元素的位置相關，如果我們記錄元素位置，顯示是符合第二個條件的。

其他可以對照代碼注釋進行理解。

柱狀圖中的最大矩形

描述：

給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。

求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。

解釋：

Snipaste_2022-09-04_16-25-50.png

Snipaste_2022-09-04_16-26-03.png

同理，首先，套一下單調棧的適用條件

• 這是一個數組，這里的條件比較隱晦，可以這樣理解，數組里的元素遇到比自己大的或者相等的，可以向右勾勒，但是遇到比自己小的，不能向右勾勒，然后求每個元素的勾勒面積的最大值，是滿足第一個條件的。
• 如果遇到比自己小的，不能向右勾勒，可以統(tǒng)計此元素的勾勒面積嗎，那就要看左邊了，左邊也都是有序且小于等于此元素的，寬度只與元素位置有關，高度只與此元素值有關，可以統(tǒng)計。統(tǒng)計后排除此元素，會對后面元素的統(tǒng)計有影響嗎，這里要注意，如果排除對后面元素是可能有影響的，因為后面元素的統(tǒng)計寬度與此元素的位置可能有關，比如2 1 5 6 2 3，2 > 1, 統(tǒng)計2然后排除，2的位置將丟失，在統(tǒng)計1的時候，1是可以勾勒2的位置的。那怎么辦，只需要保留2的位置就行了，試想如果2和1之間有多個2，我們應該保留哪一個？我們應該保留距離1最左邊的那個2的位置就行了，這樣計算1的寬度才是正確的，為了保證有序性，我們把2統(tǒng)計完成后，我們把1左邊的2全部排出，然后保留一個最左邊位置的且把它的值修改成1，當前的1也不需要進行入棧了，因為它的面積肯迪東比修改成1的那個面積統(tǒng)計的要小。

結合代碼，可以好好理解一下：

/*
柱狀圖中最大的矩形
給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。
求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。
*/

#define STACK_NUM_MAX 100000

int largestRectangleArea(int *heights, int heightsSize)
{
    int stack[STACK_NUM_MAX] = {0}; /* 記錄元素位置的單調棧 */
    int top = -1; /* 此單調棧棧頂的索引, 初始位為-1, 棧為空*/
    int max = 0;
    int area = 0;

    for (int i = 0; i < heightsSize; i++) { /* 遍歷數組 */
        /* 棧為空, 或者遇到的元素大于等于棧頂對應的元素, 還可以繼續(xù)向右勾勒*/
        if ((top < 0) || (heights[i] >= heights[stack[top]])) {
            top++;
            stack[top] = i;
            continue;
        }

        /* 棧不為空, 且遇到的元素小棧頂對應的元素, 統(tǒng)計棧頂對應的元素的面積*/
        while ((top >= 0) && (heights[i] < heights[stack[top]])) {
            area = heights[stack[top]] * (i - stack[top]);
            if (area > max) {
                max = area;
            }
            top--; /* 統(tǒng)計棧頂后出棧 */
        }
        /* 保留最后一次的棧頂, 并修改對應的元素的值為當前遇到的元素值, 當前的元素值也不必入棧, 因為它統(tǒng)計的面積必然小一些*/
        top++;
        heights[stack[top]] = heights[i];
    }

    /* 最后還要進行一次計算 */
    while (top >= 0) {
        area = heights[stack[top]] * (heightsSize - stack[top]);
        if (area > max) {
            max = area;
        }
        top--;
    }

    return max;
}