数列下标

数列下标

https://ac.nowcoder.com/acm/problem/18356

题目

给出一个数列 ,求出一个数列
其中 表示数列 右边第一个比 大的数的下标(从 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;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 10:56
点赞 评论 收藏
分享
05-12 17:00
门头沟学院 Java
king122:你的项目描述至少要分点呀,要实习的话,你的描述可以使用什么技术,实现了什么难点,达成了哪些数字指标,这个数字指标尽量是真实的,这样面试应该会多很多,就这样自己包装一下,包装不好可以找我,我有几个大厂最近做过的实习项目也可以包装一下
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务