萌新求问
查看原帖
萌新求问
651908
8NewOC楼主2023/3/3 19:58

此题能用单调栈做吗? 写了一个漏洞百出

#include<bits/stdc++.h>
using namespace std;
int n,top=0;
struct kkk{
	int x,id,ton;
}a[10001],stk[10001];
bool cmp(kkk a,kkk b){
	return a.x<b.x;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].x;
		a[i].id=i;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		if(top==0){
			top++;
			stk[top].x=a[i].x;
			stk[top].id=a[i].id;
		}
		for(int j=top;j>=1;j--){
			if(a[i].id<stk[top].id){
				top--;
			}
			else{
				top++;
				stk[top].x=a[i].x;
				j=0;
			}
		}
		a[i].ton=top;
	}
	for(int i=1;i<=n;i++){
		cout<<a[i].ton<<" ";
	}
}
2023/3/3 19:58
加载中...