单调栈

引入

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

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

过程

插入

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

例如，栈中自顶向下的元素为 $\{0,11,45,81\}$ 。

插入元素 $14$ 时为了保证单调性需要依次弹出元素 $0,11$ ，操作后栈变为 $\{14,45,81\}$ 。

用伪代码描述如下：

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

应用

题面

给出 $n$ 个数组成的数列，请你输出对于每个数，在其左边距离它最近的数，若不存在则输出 $-1$ 。

用单调递增栈，当该元素可以入栈的时候，栈顶元素就是它左侧第一个比它小的元素。

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 100010;

int h[N];

int main()
{
    int a[N];
    int n;
    cin >> n;
    int tt = 0;
    
    // 单调栈中维护的是一个单调递增的序列。
    // 一旦入栈时，有元素大于等于它，那就把这些都删掉
    // 直至满足栈底到栈顶的元素单调递增。
    while(n -- )
    {
        int m;
        scanf("%d", &m);
        
        // 因为是找第一个小的值，不是第一个不大于的值
        // 大于等于的都要删除
        while(tt && h[tt] >= m) tt--;
        // 如果删完了空了，输出 -1
        if(!tt) printf("-1 ");
        // 不空则，输出栈顶元素
        else printf("%d ", h[tt]);//栈顶元素就是左侧第一个比它小的元素。
        // 自己入栈
        h[++tt] = m;
        
    }
    
    return 0;
}```

例题：

Status

Problem

单调栈

引入

过程

插入

应用

例题：

On this page