学习笔记：单调栈

· · 算法·理论

单调栈

引入

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

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

过程

插入

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

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

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

用伪代码描述如下：

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

使用

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

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

例题

洛谷 P5788【模板】单调栈

题目描述

给出项数为 n 的整数数列 a_{1 \dots n}。

定义函数 f(i) 代表数列中第 i 个元素之后第一个大于 a_i 的元素的下标，即 f(i)=\min_{i<j\leq n, a_j > a_i} \{j\}。若不存在，则 f(i)=0。

试求出 f(1\dots n)。

输入格式

第一行一个正整数 n。

第二行 n 个正整数 a_{1\dots n}。

输出格式

一行 n 个整数表示 f(1), f(2), \dots, f(n) 的值。

#include <iostream>
#include <stack>
#define MAXN 3000005
using namespace std;
int n;
int a[MAXN];
int f[MAXN];
stack <int> s;
int read(){
    int t = 1, x = 0;char ch = getchar();
    while(!isdigit(ch)){if(ch == '-')t = -1;ch = getchar();}
    while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * t;
}
void write(int x){
    if(x < 0){putchar('-');x = -x;}
    if(x >= 10)write(x / 10);
    putchar(x % 10 + '0');
}
int main(){
    n = read();
    for(int i = 1 ; i <= n ; i ++)a[i] = read();
    for(int i = n ; i >= 1 ; i --){
        while(!s.empty() && a[s.top()] <= a[i])s.pop();
        if(!s.empty())f[i] = s.top();
        s.push(i);
    }
    for(int i = 1 ; i <= n ; i ++){
        if(i != 1)putchar(' ');
        write(f[i]);
    }
    putchar('\n');return 0;
}