C++栈

这里讲 STL 中的栈。

图片

栈的常用函数（成员函数）

• push(x):将元素 $x$ 压入栈顶。
• pop():将栈顶元素弹出。
• top():返回栈顶元素。
• size():返回栈中元素的个数。
• empty():判断栈是否为空。

注意：STL 中的栈常数有点大，而且在栈内没有元素时使用pop()函数或top()会RE，如果不嫌麻烦，可以用数组模拟。

例题

请模拟一个栈。将有 $t$ 次操作，每次操作至少会给你一个 $op$。每输出一个数换一次行.
分为三种操作：

1. 会在给你一个 $x$，请将 $x$ 压入栈顶。
2. 如果栈内是空的，请输出 RE 并不再操作，否则输出栈顶元素并弹出。
3. 输出元素个数。

代码

# include <bits/stdc++.h>
using namespace std;
int t, op, x;
stack <int> st;
int main()
{
	cin >> t;
	while(t --)
	{
		cin >> op;
		if(op == 1)
		{
			cin >> x;
			st.push(x);
		}
		else if(op == 2)
		{
			if(st.empty())
			{
				cout << "RE" << "\n";
				return 0;
			}
			cout << st.top() << "\n";
			st.pop();
		}
		else
		{
			cout << st.size() << "\n";
		}
	}
	return 0;
}

单调栈

单调栈是一种特殊的栈，它的元素是单调递增或单调递减的。

单调栈的主要作用是在一个序列中找到每个元素左边或右边第一个比它小或大的元素。

单调栈的实现方法是使用一个栈来存储元素，每次将一个元素入栈时，将栈中比它小的元素弹出，直到栈顶元素比它大或栈为空。

单调栈的时间复杂度为 $O(n)$，其中 $n$ 是序列的长度。

单调栈的应用非常广泛，例如在计算最大矩形面积、最大子矩阵和最大子数组和、离线 $RMQ$ 等问题中，都可以使用单调栈来解决。

单调栈的实现方法如下：

1. 创建一个空栈。
2. 遍历序列中的每个元素。
3. 如果栈为空或栈顶元素比当前元素小，则将当前元素入栈。
4. 如果栈顶元素比当前元素大，则将栈顶元素弹出。
5. 重复步骤 4，直到栈为空或栈顶元素比当前元素小。
6. 将当前元素入栈。
7. 重复步骤 3 到 6，直到序列中的所有元素都被遍历。
8. 输出。

例题：洛谷 P5788 【模板】单调栈

P5788 【模板】单调栈

题目背景

模板题，无背景。

2019.12.12 更新数据，放宽时限，现在不再卡常了。

题目描述

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

输入输出样例 #1

输入 #1

5
1 4 2 3 5

输出 #1

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$。

代码

# include <bits/stdc++.h>
using namespace std;
int n , a , ans;
stack <int> st;
int main()
{
	cin >> n;
	for(int i = 1 ; i <= n ; i ++)
	{
		cin >> a[i];
		while(!st.empty() && a[i] > a[st.top()])
		{
			ans[st.top()] = i;
			st.pop();
		}
		st.push(i);
	}
	for(int i = 1 ; i <= n ; i ++)
	{
		cout << ans[i] << " ";
	}
	return 0;
}