单调栈

⬅ 返回

1、使用题型

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

2、思路

用单调递增栈，当该元素可以入栈的时候，栈顶元素就是它左侧第一个比它小的元素。 以：3 4 2 7 5 为例，过程如下：

3、代码实现

#include <iostream>
#include<stack>
using namespace std;
const int N = 1e6+10;
int a[N];
stack<int> st;
 
int main(){
	
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		while(st.size()!=0 && st.top()>=a[i])//如果栈顶元素大于当前待入栈元素，则出栈
		    st.pop();
		if(st.size()==0)//如果栈空，则没有比该元素小的值。
		    cout<<-1<<" ";
		else
		    cout<<st.top()<<" ";//栈顶元素就是左侧第一个比它小的元素。
		st.push(a[i]);
		
	}
}