单调栈

顾名思义单调栈就是具有单调性的栈

常见模型：找出每个数左边离它最近的比它大/小的数

1. 【算法】

int stk[N],tt = 0;// 栈中存数据for (int i = 1; i > x;    while (tt && stk[tt] >= x) tt -- ;// 左边比它小的数    stk[ ++ tt] = i;// 把当前值放在合适地方}

2. 【应用一】
   直方图中最大的矩形
   算法思想:
   ① 以每一个矩形的高为标准，找出左右两边第一个小于此矩形高的矩形，枚举所有
   的矩形，找出最大面积。
   ② 利用单调栈，进行预处理将每个矩形左右两边的第一个小于此矩形高的矩形。

#include #include #include #include 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 = 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 #include #include using namespace std;typedef long long LL;typedef pair 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 = 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 > n >> m;    for (int i = 0; i < n; i ++){        for (int j = 1; j > c;   // 这里建议用cin 自动省略空格回车            if (c == 'R') h[j] = 0;  // 遇R高度就变0            else h[j] += 1;        }        solve();    }    printf("%d\n", res * 3);    return 0;}