洛谷P5788

Posted by

https://www.luogu.com.cn/problem/P5788

//luogu P5788
#include <bits/stdc++.h>

using namespace std;

struct node
{
    int val, pos;
};

stack <node> s;
int n, ans[3000010];

int main()
{
    scanf("%d",&n);
    node num, item2;
    for ( int i = 1; i <= n; i ++ )
    {
        scanf("%d",&num.val);
        num.pos = i;
        if ( s.empty() ) 
        {
            s.push(num);
        }
        else
        {

            item2 = s.top();
            while ( item2.val < num.val )
            {
                //printf("item = %d\n",item);
                ans[item2.pos] = num.pos;
                s.pop();
                if ( s.empty() ) break;
                item2 = s.top();
            }
            s.push(num);
        } 
    }
    item2 = s.top();
    ans[item2.pos] = 0;
    for ( int i = 1; i <= n; i ++ ) printf("%d ",ans[i]);
    return 0;
}

github:https://github.com/ShaoChenHeng/codeOfACM/blob/cf6cc30444d8088fc80aac27af18023f0245440a/linearStruct/monotonousStack/modelCode.cpp

Leave a Reply

邮箱地址不会被公开。 必填项已用*标注