地址:https://www.acwing.com/problem/content/602/
既然是离自己最近,可以想到栈
对于当前数,把它左边数的视为栈。
每次ai与栈顶比较,
如果发现栈顶<ai,说明它可以被栈顶仰视,记录下标。同时清掉栈顶。为什么要清掉呢?因为题目要求的是找最近,既然栈顶已经找到最近答案,后续就用不到它了,所以清掉即可。
否则,while结束。为什么结束?因为栈顶大于>=ai的话,栈里其他的元素也一定大于等于ai,因为我们建立的是一个单调队列。假设有a1<a2,那么根据第一步,a1被清掉,再次加入一个a3,而且a3<a2,那么此时栈有:a2,a3。再加入一个a4<a3,那么a4也只能入栈,栈里的元素,均大于a4,while也就没必要继续了。
#include<cstdio> #include<cstring> #include<vector> #include<set> #include<stack> #include<algorithm> #include<iostream> #include<vector> using namespace std; typedef long long ll; const int maxn=1e5+10,maxn2=31*maxn; int st[maxn],tt,n,a[maxn],b[maxn]; stack<pair<int,int> > s; struct node { int x,id; }h[maxn]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { while(!s.empty()&&a[i]>s.top().first) { b[s.top().second]=i; s.pop(); } s.push(make_pair(a[i],i)); } for(int i=1;i<=n;i++) { cout<<b[i]<<endl; } }