#include<bits/stdc++.h> using namespace std; const int N = 100010; int n, a[N], stk[N], tt = 0,ans[N]; int main(){ cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; } for(int i = n; i >= 1; i--){ while(tt && a[i]>= a[stk[tt] ]) tt--;

    if(tt) ans[i]=stk[tt];
    else ans[i]=0;
    stk[++tt] =i;
}
for(int i=1;i<=n;i++){
	cout<<ans[i]<<endl;
}

return 0; }

1 条评论

  • @ 2025-5-11 14:32:17
    单调栈存下表
    ```language
    #include<bits/stdc++.h>
    using namespace std;
    const int N = 100010;
    int n, a[N], stk[N], tt, ans[N];
    int main(){
        cin >>n;
    	for(int i = 1; i <= n; i++) cin >> a[i];
    	for(int i = n; i >= 1; i--){
    		while(tt && a[i] >= a[stk[tt]]) {
                tt--;
            }
    		if(tt) ans[i] = stk[tt];
    	    else ans [i] = 0;
            stk[++tt] = i;
        }
    	for(int i = 1; i <= n; i++){
            cout << ans[i] << endl;
        }  
    	return 0;
    }
    
    • 1

    信息

    ID
    1586
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    77
    已通过
    27
    上传者