Codeforces(C2. Skyscrapers (hard version))(单调栈)

原题链接:https://codeforces.ml/contest/1313/problem/C2

单调栈讲解博客

利用单调栈,可以找到从左(或者右)遍历第一个比它小(或者大)的元素的位置。

模板:

stack<int> s;
for(int i = 1; i <= n; ++i)
{
    while(s.size() && a[s.top()] > a[i])
    { s.pop(); }
    if(s.empty()) 
    {
       c[i] = 0;
    } 
    else 
    {
       c[i] = s.top();
     } 
    s.push(i);
}

 

原题代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[500010],u[500010],v[500010];
stack<ll> s;
void init()
{
    while(!s.empty())
    {s.pop();}
}
int main()
{
    ll n;
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
    {scanf("%lld",&a[i]);}
    for(int i=0;i<n;i++)
    {
        while(s.size()&&a[s.top()]>a[i])
        {
            s.pop();
        }
        if(s.empty())
        {u[i]=a[i]*(i+1);}
        else
        {u[i]=u[s.top()]+(i-s.top())*a[i];}
        s.push(i);
    }
    init();
    for(int i=n-1;i>=0;i--)
    {
        while(s.size()&&a[s.top()]>a[i])
        {
            s.pop();
        }
        if(s.empty())
        {v[i]=a[i]*(n-i);}
        else
        {v[i]=v[s.top()]+(s.top()-i)*a[i];}
        s.push(i);
    }
    ll maxx=-1,ans,ip;
    for(int i=0;i<n;i++)
    {
        ans=u[i]+v[i]-a[i];
        if(ans>maxx)
        {
            maxx=ans;
            ip=i;
        }
    }
    for(int i=ip-1;i>=0;i--)
    {
        if(a[i]>a[i+1])
        {a[i]=a[i+1];}
    }
    for(int i=ip+1;i<n;i++)
    {
        if(a[i]>a[i-1])
        {a[i]=a[i-1];}
    }
    for(int i=0;i<n;i++)
    {
        printf("%lld ",a[i]);
    }
    printf("\n");
    return 0;
}

123

点赞

发表评论

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