单调栈笔记

单调栈笔记

单调栈，顾名思义，就是把元素按照严格单调的顺序存在栈中（从「栈顶」到「栈底」）

可以加速查找数组中满足特定条件的数的过程，例如：

• 寻找左侧第一个比当前元素大的元素
• 寻找左侧第一个比当前元素小的元素
• 寻找右侧第一个比当前元素大的元素
• 寻找右侧第一个比当前元素小的元素

可以有效的将嵌套搜索的 \(O(n^2)\) 的时间复杂度优化到 \(O(n)\)

关于栈的实现，可以使用 \(STL\) 中的 stack 库实现，也可以利用数组和栈顶指针进行模拟操作（速度略快）

这里举一道例题具体说明：题目如下

题目描述

给出项数为 \(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)\) 的值

样例输入

5
1 4 2 3 5

样例输出

2 5 4 5 0

数据规模与约定

对于 \(30\%\) 的数据，\(n\leq 100\)

对于 \(60\%\) 的数据，\(n\leq 5 \times 10^3\)

对于 \(100\%\) 的数据，\(1 \le n\leq 3\times 10^6\)，\(1\leq a_i\leq 10^9\)

首先介绍第一种方法——利用stack库实现：

题目要求查找 \(a_i\) 之后的元素，所以我们需要先将所有数据存进数组，然后反向搭建单调栈

for (int i = 1; i <= n; i++) scanf("%d", &input[i]);//存入数组input

反向操作：

for (int i = n; i > 0; i--) {
	while (!stk.empty() && inp[stk.top()] <= inp[i]) stk.pop();
	ans[i] = stk.empty() ? 0 : stk.top();
	stk.push(i);
}

逐语句解释原理：

while (!stk.empty() && input[stk.top()] <= input[i]) stk.pop();

当 stk 栈不为空并且栈顶元素所存的下标值使得input[stk.top()] <= input[i]时

即当前选择的input[i]的值，大于等于input[stk.top()] 的值时，弹出栈顶元素

stk.push(i);

搭配赋值语句，将下标 i 存进栈中，这样我们就能保证栈中的元素是严格单调递增的

在退出 for 遍历前，还需要把查找到的目标元素的下标存进 ans 数组，便于输出答案

ans[i] = stk.empty() ? 0 : stk.top();

这里使用三元运算符，若 stk 栈为空，则把 ans[i] 赋值为 \(0\) ，满足题意

若不为空，则将栈顶元素存储的下标值赋值给 ans[i]

完整代码如下：从下标为 \(1\) 开始，符合题意

int inp[3000010], ans[3000010];
stack<int> stk;

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &inp[i]);
	for (int i = n; i > 0; i--) {
		while (!stk.empty() && inp[stk.top()] <= inp[i]) stk.pop();
		ans[i] = stk.empty() ? 0 : stk.top();
		stk.push(i);
	}
	for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
	return 0;
}

接下来介绍模拟栈的实现：

首先定义一个数组空间模拟栈空间，以及一个指针模拟栈顶游标

int stk[3000010],tt;

和利用stack库的操作只有在实现单调栈的循环中有所不同：

for (int i = n; i > 0; i--) {
	while (tt && a[stk[tt]] <= a[i]) tt--;
	ans[i] = tt ? stk[tt] : 0;
	stk[++tt] = i;
}

同样的，首先判断模拟栈空间是否为空，以及当前元素是否大于等于栈顶元素所映射的元素值：

tt && a[stk[tt]] <= a[i]

循环到使栈内元素严格单调递增或空栈时退出

同理，可以写出由栈顶游标 tt 所实现的pop(),top(),empty(),push()操作

我们所定义的栈空间实际上是在stk[0]~stk[tt]的空间内，所以移动栈顶游标的位置，就是对栈顶元素进行操作

完整代码如下：

int a[3000010],stk[3000010],ans[3000010],tt;

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = n; i > 0; i--) {
		while (tt && a[stk[tt]] <= a[i]) tt--;
		ans[i] = tt ? stk[tt] : 0;
		stk[++tt] = i;
	}
	for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
	return 0;
}

总结：

单调栈就是将无序的元素队列，选出其中的某些元素，构成一个元素值随元素下标的单调变化而单调变化的一个序列

优化实现 \(O(n)\) 的查找时间复杂度