单调栈

前言

何为单调栈？顾名思义，单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出。

为了描述方便，以下举例及伪代码以维护一个整数的单调递增栈为例。

插入

将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。

使用

自然就是从栈顶读出来一个元素，该元素满足单调性的某一端。

例如举例中取出的即栈中的最小值。

• 伪代码

insert x
while !sta.empty() && sta.top() < x
    sta.pop()
sta.push(x)

• 实现代码：

#include <iostream>
using namespace std;
const int N = 3e6 + 5;
int h[N], res[N];
struct stack{//手写栈
    int a[N];
    int t = 0;
    inline void push(int x){a[++t] = x;}
    inline int top(){return a[t];}
    inline void pop(){t--;}
    inline int empty(){return t == 0 ? 1 : 0;}
}st;
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = n; i >= 1; i--){
        while(!st.empty() && h[st.top()] <= h[i]) st.pop();
        st.empty() ? res[i] = 0 : res[i] = st.top();
        st.push(i);
    }
    for(int i = 1; i <= n; i++) cout << res[i] << " ";
    return 0;
}