数列下标

题目

给出一个数列 ，求出一个数列 。
其中 表示数列 中 右边第一个比 大的数的下标（从 1 开始计数），没有找到这一个下标 就为 0。

解题思路

在从右向左遍历数组 A 时维护一个栈。这个栈存储数列 A 的下标。
如果栈非空，且栈顶的元素（下标）所代表的值小于等于当前的值，
这表示栈顶下标 sta.top() 比当前的下标大，且下标值 A[sta.top()] 小于等于当前值 A[i]，就可以弹出栈顶元素，压入当前的下标。
当栈为空时，表示数列 A 的右边没有元素大于当前元素，当前所求的值是 0。

C++代码

#include<cstdio>
#include<vector>
#include<stack>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    vector<int> A(n);
    for(int i=0; i<n; ++i){
        scanf("%d", &A[i]);
    }
    stack<int> sta;
    vector<int> ans(n, -1);
    for(int i=n-1; i>=0; --i){
        while(!sta.empty() && A[sta.top()]<=A[i])
            sta.pop();
        if(!sta.empty())
            ans[i] = sta.top();
        sta.push(i);
    }
    for(int i=0; i<n; ++i){
        printf("%d ", ans[i]+1);
    }
    return 0;
}