前往：我自己搭建的博客
题目
洛谷P5788单调栈
题解
从左往右扫描序列，并维护一个栈，栈内的元素目前未找到比它大的。每次遇到新元素时，将栈内比它小的元素更新并出栈。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=3e6+5;
int n,num;
int f[maxn];
stack<pair<int,int> > s; //下标/数值
inline int read()
{
int s=0; char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
num=read();
while(s.size()&&num>s.top().second) f[s.top().first]=i,s.pop(); //注意s.size要写在前面
s.push(make_pair(i,num));
}
for(int i=1;i<=n;i++) printf("%d ",f[i]);
return 0;
}
