二.1 数据结构—单调栈
单调栈题型
在一个数组中a[i]左边离它最近且小于它的数..
暴力做法
for (int i=0;i<n;i++)
for(int j=i-1;j>=0;j--)
if(a[j]>a[i])
{
cout<<a[j]<<endl;
break;
}
单调栈
假如,在a[i]之前,存在一个逆序关系(单调减)
x<y but a[x]>a[y] 那么a[x]永远不会是答案,所以我们要把逆序的删掉
最后留下的是单调递增的序列,我们只需要从栈顶开始找小于a[i]的即可
用单调递增栈,当该元素可以入栈的时候,栈顶元素就是它左侧第一个比它小的元素。
#include<iostream>
using namespace std;
const int N=1e5+10;
int stk[N],tt=-1;
int main()
{
int n;cin>>n;
while(n--)
{
int x;cin>>x;
while(tt!=-1 && stk[tt]>=x) tt--; //放入的值小于等于栈顶,就把栈顶删去
if(tt!=-1) cout<<stk[tt]<<" ";
else cout<<-1<<" ";
stk[++tt]=x;
}
return 0;
}