单调栈

(单调栈模板题) 题目描述 给定一个长度为n的整数数组a，你需要求出每个元素的左边离它最近且比它小的元素。

输入描述 第一行：一个整数n(1≤n≤2×10^5) 第二行：n个整数，表示整数数组a.(1≤a≤10^9)

输出描述 共一行，n个整数，表示每个元素的左边第一个比它小的元素，若不存在则为−1。

输入样例1 5 7 8 5 6 7 输出样例1 -1 7 -1 5 6

我们可以使用STL中的stack实现 思路主要为将数组中的数值于栈中的数值进行对比，但栈中的数组比数组中的值大时，我们需要舍弃栈中的数，否则将数组中的值压入栈中 代码示例:

#include<iostream>
#include<stack>
using namespace std;
const int N = 2e5;
int a[N], b[N];
int main()
{
	std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i];

	stack<int>q;

	for (int i = 1; i <= n; i++) {
		while (!q.empty() && q.top() >= a[i])q.pop();
		if (q.empty())b[i] = -1;
		else b[i] = q.top();
		q.push(a[i]);
	}
	for (int i = 1; i <= n; i++)cout << b[i] << " ";
	return 0;
}

使用stack是一种选择，但是更推荐使用数组模拟来实现单调栈，因为数组能进行更多操作，对于题目的适应与灵活度更高。但是因为数组空间固定要注意数组栈的溢出问题。 下面给出数组实现的代码:

#include<iostream>
using namespace std;
const int N = 2e5;
int a[N], b[N], stk[N], top;
int main()
{
	std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i];

	for (int i = 1; i <= n; i++) {
		while (top && a[stk[top]] >= a[i])top--;
		if (top)b[i] = a[stk[top]];
		else b[i] = -1;
		stk[++top] = i;
	}
	for (int i = 1; i <= n; i++)cout << b[i] << " ";
	return 0;
}