洛谷 P5788 【模板】单调栈
·
思路和之前那个单调队列差不多，只遍历一遍，所有数据都取一次，不满足条件的就踢出去。
1 2 3 4 3 2 1 2 3 4 从后面找到比自己大的第一个数因为要在后面找最大值，所以不能从前面开始遍历。
upd：2023-12-6，可以从前往后遍历，记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
把所有数都取出来，比如后面4个1 2 3 4先取出来，依次输出就行（4后面没东西了，直接是0）
下一个2来了，第一个大的是3，也就是说1 2 3 4，小于等于2的都不需要了（很明显了吧，前面都出现2了，那后面的1是永远不会被遍历到了，所以小于等于2的都消失）
一直弹出的都是最左边的输出的也是最左边的，和栈类似，所以可以用栈来实现。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN=3e6+1;
int n,a[MAXN],f[MAXN],maxx;
stack<pair<int,int>>s;//下标 数据
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
s.push({n,a[n]});
for(int i=n-1;i>=1;i--){
while(!s.empty()&&a[i]>=s.top().second)s.pop();
if(!s.empty())f[i]=s.top().first;
s.push({i,a[i]});
}
for(int i=1;i<=n;i++)
printf("%d ",f[i]);
return 0;
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
0
0- 0
已为社区贡献9条内容
所有评论(0)