单调栈的使用场景
判断左边或者右边第一个比其小/大的数字
单调栈的原理
顾名思义,就是栈里面的元素满足单调上升或者单调下降
拿这题来举例,取左边最近较小元素,适用单调下降栈
为什么能用单调栈
这题有一个性质,如果下标满足i小于j
且同时满足a[i]>=a[j],a[i]是绝对不会满足题意的!可以根据这一点考虑我们的算法
设有指针i,如果指向的当前元素小于等于栈顶,就弹出直到为空或者小于栈顶。此时取栈顶元素,一定是满足题意的
举个例子:[1,2,3,4,5]栈顶元素始终为1
而[5,4,3,2,1]栈顶元素也依次为[5,4,3,2]
本人特别标注:一定不要忘了等于这个条件,因为有这种情况[1,3,1]
当遍历到第三个数时,必须将栈中的1弹出,因为题目要求必须严格小于
如果等于时不弹出,就会导致不符合题意
//参考y总上课代码自己写成
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10e5+10;
int st[N],tt;
int n;
int main()
{
cin>>n;
for (int i = 0; i < n; i ++ )
{
int x;
scanf("%d", &x);
while(tt&&st[tt-1]>=x) tt--;
if(!tt) cout<<"-1"<<" ";
else cout<<st[tt-1]<<" ";
st[tt++]=x;
}
return 0;
}