單調棧

顧名思義單調棧就是具有單調性的棧

常見模型：找出每個數左邊離它最近的比它大/小的數

1. 【演算法】

int stk[N],tt = 0;	// 棧中存數據
for (int i = 1; i <= n; i ++){
    int x; cin >> x;
    while (tt && stk[tt] >= x) tt -- ;	// 左邊比它小的數
    stk[ ++ tt] = i;	// 把當前值放在合適地方
}

2. 【應用一】
   直方圖中最大的矩形
   演算法思想:
   ① 以每一個矩形的高為標準，找出左右兩邊第一個小於此矩形高的矩形，枚舉所有
   的矩形，找出最大面積。
   ② 利用單調棧，進行預處理將每個矩形左右兩邊的第一個小於此矩形高的矩形。

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 100010;
int n;// h: 高度 q: 單調棧->記錄h的下標 l: 左邊符合條件距離 r: 右邊符合條件距離
int h[N],q[N],l[N],r[N];
void solve(){
    while (scanf("%d", &n),n){
        for (int i = 1; i <= n; i ++) scanf("%d",&h[i]);
        h[0] = h[n + 1] = -1;      // 預處理要邊界條件
        // 找出左邊第一個高度小於當前
        int tt = -1;
        q[++ tt] = 0;   // 下標 0
        for (int i = 1; i <= n; i ++){
            while (h[q[tt]] >= h[i]) tt --;//維護好單調棧: 找到棧中第一個小於當前值的數據
            l[i] = i - q[tt];   // 記錄i左邊第一符合條4 件的數據距離
            q[++ tt] = i;       // 當前值下標入棧
        }
        // 同理求右邊
        tt = -1;
        q[++ tt] = n + 1;
        for (int i = n; i >= 1; i --){
            while (h[q[tt]] >= h[i]) tt --;
            r[i] = q[tt] - i;
            q[++ tt] = i;
        }
        LL res = 0;
        for (int i = 1; i <= n; i ++)
            res = max(res, (LL)h[i] * (l[i] + r[i] - 1));// - 1是因為計算左右兩邊就多加一個h[i]
        printf("%lld\n", res);
    }
}
int main(){
    solve();
    return 0;
}

3. 【應用二】
   城市游戲
   演算法思想:
   聯想【應用一】，統計每一行向上的高度，再利用應用一單調棧的解題方法，遍歷n行，求出最優解。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;

const int N = 1010;
int n,m,res;
int h[N],q[N],l[N],r[N];
// 這裡就是【應用一】一行的解題方法
void solve(){
    for (int i = 0; i <= m + 1; i ++)q[i] = 0;
    h[0] = h[m + 1] = -1;
    int tt = -1;
    q[++ tt] = 0;
    for (int i = 1; i <= m; i ++){
        while (h[q[tt]] >= h[i]) tt --;
        l[i] = i - q[tt];
        q[++ tt] = i;
    }
    tt = -1;
    q[++ tt] = m + 1;
    for (int i = m; i >= 1; i --){
        while (h[q[tt]] >= h[i]) tt --;
        r[i] = q[tt] - i;
        q[++ tt] = i;
    }
    for (int i = 1; i <= m; i ++)
        res = max(res, h[i] * (l[i] + r[i] - 1));
}
int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i ++){
        for (int j = 1; j <= m; j ++){
            char c; cin >> c;   // 這裡建議用cin 自動省略空格回車
            if (c == 'R') h[j] = 0;  // 遇R高度就變0
            else h[j] += 1;
        }
        solve();
    }
    printf("%d\n", res * 3);
    return 0;
}