$$单调栈$$

栈是一种先进先出的基础数据结构，这里不多做简介

// 给出栈的基本操作
int stk[N], top;

// 进栈
void push(int k){
    stk[++top] = k;
}

// 出栈
void pop(){
    if(!top) puts("There is no 元素(滑稽，英语太差)"); // 判断栈是否为空
    else -- top;
}

// 取出栈顶元素
void get(){
    if(!top) puts("There is no 元素");
    else cout << stk[top] << endl;
}

单调栈常用于:给定一个序列，对于每个数寻找其左边（或右边）第一个比它大（或比它小）的数。时间复杂度$O(n)$

其核心思想是将不可能的情况排除

例题1

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 3e6 + 5;

int n, h[N];
int res[N] ,stk[N], top;
// stk 存下标 res 存满足条件的最小值

inline int read(int &x){
    x = 0; char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}

int main(){
    read(n);
    for(int i = 1; i <= n; i++) read(h[i]);

    for(int i = n; i>= 1; i--){
        while(top && h[stk[top]] <= h[i]) top --; //新数入栈, 判断已经进栈的数是否满足单调性

        if(!top) res[i] = 0;   // 栈空 说明没有比这个数 更大
        else res[i] = stk[top];

        stk[++ top] = i;
    }
    for(int i = 1; i <= n; i++) printf("%d ", res[i]);

    return 0;
}

例题2

分析:求最大的面积,所选矩形里面的直方条是单调增的,选取一个矩形,向左向右扩展,扩展的值一定要 >= 选取的矩形, 这样扩展的矩形就可以委屈自己来和选取的矩形高度持平, 如果 扩展的值 < 选取的矩形, 他就不配了(来委屈都没人要)

问题转化成，从选取的矩形(高度 $h_i$),向两边找， 一直找到（两个方向）小于$h_i$的最近的矩形(假设左边满足该条件的矩形为第$l_{k1}$,右边…为$r_{k2}$),这向右和向左的距离即为最大的面积的宽$ (r_{k2} - l_{k1} - 1) * h_i $

#include <iostream>
#include <stack>

using namespace std;

const int N = 100005;
typedef long long ll;

int n, w[N];
int l[N], r[N], stk[N];
// l --> 向左扩展满足条件 r --> 向右扩展满足条件   stk  --> 单调栈
int main(){

    while(cin >> n, n){

        for(int i = 1; i <= n; i++) cin >> w[i];

        w[0] = w[n + 1] = - 1;  // 省去处理边界的麻烦,（边界元素可能是 0）

        int tt = 0;
        stk[0] = 0;

        for(int i = 1; i <= n; i++){
            while(w[i] <= w[stk[tt]]) tt --; // 当前数比单调栈的 栈顶元素 小,不满足单调栈性质, 出栈
            l[i] = stk[tt];  // 记录
            stk[++ tt] = i;  // 进栈
        }
        tt = 0; stk[0] = n + 1;
        for(int i = n; i >= 1; i--){
            while(w[i] <= w[stk[tt]]) tt --;
            r[i] = stk[tt];
            stk[++ tt] = i;
        }

        ll res = 0;
        for(int i = 1; i <= n; i++)
        res = max(res, (ll)(r[i] - l[i] - 1) * w[i]);

        cout << res << endl;
    }

    return 0;
}