单调栈的思想及应用

思想及实现

定义

单调栈，顾名思义就是单调的栈，栈内的元素是单调递增的或者单调递减的。

举例

以一个单调递增的栈为例，给定一个数组$7,3,1,2,8,4,9$，将其中的元素依次放入栈中

得到一个形如$1,2,4,9$的栈

由于$1$以前的数都更小，就得在插入$1$前全部弹出

如何维护

以单调递减（严格）的单调栈为例，要想维护栈的单调性，只需要在入栈、出栈的时候，保证入栈元素小于栈顶元素。

所以，假设我们当前要入栈的数为x

如果栈顶元素比x大，那么我们直接入栈即可
否则，栈顶元素小于等于x时，我们可以通过不断弹出栈顶元素的方式来保证入栈前栈顶元素大于x

那么，入栈的代码就能写出来了

int stk[N], tt = -1;
void push(int x) {
    while (tt >= 0 && x >= stk[tt]) tt --;
    stk[++tt] = x;
}

出栈的代码和普通的栈一样，不用变

int stk[N], tt = -1;
void pop(int x) {
	if (tt >= 0) tt --;
}

与单调栈的区别

如果没有左边界，考虑单调栈，如果有左边界，考虑单调队列。

模板题

P5788 【模板】单调栈 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

由于题目中要求的是数组下标，所以栈内维护下标，利用索引的方式比较栈顶和待插入元素大小

参考代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3e6 + 10;

int n;
int a[N];
int stk[N], tt;
int ans[N];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

	for (int i = n; i >= 1; i -- ) {
        // 当栈内有元素时，如果无法保证单调，则弹出栈顶
		while (tt && a[stk[tt]] <= a[i]) tt --;
		ans[i] = stk[tt]; // 更新答案
        // 入栈
		stk[++ tt] = i;
	}
	for (int i = 1; i <= n; i ++ )
		printf("%d ", ans[i]);

	return 0;
}