单调栈

1.单调栈模板

常见模型：找出每个数左边离它最近的比它大/小的数

int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

2.示例

给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出-1。

输入格式

第一行包含整数N，表示数列长度。
第二行包含N个整数，表示整数数列。

输出格式

共一行，包含N个整数，其中第i个数表示第i个数的左边第一个比它小的数，如果不存在则输出-1。
数据范围1≤N≤105, 1≤数列中元素≤109

输入样例：

5
3 4 2 7 5

输出样例：

-1 3 -1 2 2

代码：

#include <iostream>
using namespace std;

const int N = 100010;
int stk[N], tt = 0;

int main()
{
	ios::sync_with_stdio(false);

	int n, x; cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> x;
		while (tt > 0 && stk[tt] >= x) --tt;   //将大于x的元素全部出栈,
		if (tt > 0) cout << stk[tt] << ' ';
		else cout << "-1" << ' ';
		stk[++tt] = x;
	}

	return 0;
}

运行结果：

本文地址：https://blog.csdn.net/weixin_43202635/article/details/107371929