CodeForces - 1313C Skyscrapers (单调栈)

传送门：

题目描述

一排大楼，需要满足这样一个条件，每个大楼只能存在一侧比它高。

思路分析

经过分析，可以想到这实际上就是一个单峰，一个最大值，左边不严格递减，右边不严格递增
可以通过单调栈预处理出每个点作为最大值的贡献，最后枚举得到这个最大的位置

样例输入

3
10 6 8

样例输出

10 6 6

AC代码

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N=5e5+10;

ll a[N],ans[N],le[N],ri[N];

int n,top;
pair<ll,ll>st[N];

void init(ll *x) {
    ll sum=0;
    st[top=0]=mp(0,0);
    for(int i=1; i<=n; i++) {
        while(top>0 && a[i]<st[top].first) {
            sum-=st[top].first*(st[top].second-st[top-1].second);
            --top;
        }
        sum+=a[i]*(i-st[top].second);
        st[++top]=mp(a[i],i);
        x[i]=sum;
    }
}

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i];

    init(le);
    reverse(a+1,a+1+n);
    init(ri);
    reverse(a+1,a+1+n);
    reverse(ri+1,ri+1+n);

    int pos=0;
    ll ma=0;
    for(int i=1; i<=n; i++) {
        ll sum=le[i]+ri[i]-a[i];
        if(sum>ma) {
            ma=sum;
            pos=i;
        }
    }
    ans[pos]=a[pos];
    for(int i=pos+1; i<=n; i++)
        ans[i]=min(ans[i-1],a[i]);
    for(int i=pos-1; i>=1; i--)
        ans[i]=min(ans[i+1],a[i]);
    for(int i=1; i<=n; i++)
        cout<<ans[i]<<" ";





    return 0;
}