很少单独写一道题的题解,但是这题的解题方法是比较惊艳到我的。

此题可以作为leetcode常出题“山脉数组”的延伸。之前貌似也遇到过相似题目,无法得解,现在了却了之前不会的遗憾。

Codeforces 1313C2 - Skyscrapers

单调栈是我在lertcode做题过程中经常出现的名词,但在竞赛过程中一直不得见,直到寒假camp讲到此类应用。

这道题的实质是给出一串数组,让你把他变成山脉数组(可以理解为中间有一个最高元素,依次向两旁越来越低,形似山脉)且各元素相加和最大。

o(n^2)比较常规的处理方法就是枚举出这个最高元素,从而按照规则处理,比较出最大值。但是题目中n的范围是50000,因此这个复杂度最高为O(nlogn)。而使用单调栈处理,这个复杂度基本达到o(n),且不可能被卡常。

为什么我们需要使用单调栈?单调栈可以帮助我们找到一段单调递增/递减的区间,那么在此题中,这段单调递减区间是不是最后都变成了区间内最小值才符合要求?

我们需要对数组进行正反两遍处理:

  • 数组 l[i] 表示:以楼房 i 为峰值时,其左边(包括自己)所有楼房的总层数。

  • 数组 r[i] 表示:以楼房 i 为峰值时,其右边(包括自己)所有楼房的总层数。

先讨论 l[i] 数组的求法,对于楼房 i 而言,如果m[i]是1~i中的最小值,那么 l[i]=i∗a[i];

否则,若 j 为 i 前面,满足:a[j] < a[i]且(i−j)最小,那么 l[i]=l[j]+a[i]∗(i−j)。

r[i] 的求法同理。

那么维护这段区间只需要用上单调栈就迎刃而解了。

代码如下:

#include<bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
#define ll long long
#define U unsigned
#define sqr(x) ((x)*(x))
#define mem(x,y) memset(x,y,sizeof(x))
#define scd(x) scanf("%d",&x)
#define scs(x) scanf("%s",&x)
#define prd(x) printf("%d",x)
#define prs(x) printf("%s",x)
#define rep(x,a,b) for(int x=a;x<b;x++)
#define rep0(x,n) for(int x=0;x<n;x++)
#define rep1(x,n) for(int x=1;x<=n;x++)
#define per(x,a,b) for(int x=a;x>=b;x--)
#define ls rt<<1
#define rs rt<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
const int INF=0x3f3f3f3f;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

ll a[500005],l[500005],r[500005];
stack<ll>s;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        while(!s.empty()&&a[s.top()]>a[i]) s.pop();
        if(s.empty()) l[i]=1ll*i*a[i];
        else l[i]=l[s.top()]+1ll*(i-s.top())*a[i];
        s.push(i);
    }
    while(!s.empty()) s.pop();
    for(int i=n;i>0;i--)
    {
        while(!s.empty()&&a[s.top()]>a[i]) s.pop();
        if(s.empty()) r[i]=1ll*(n-i+1)*a[i];
        else r[i]=r[s.top()]+1ll*(s.top()-i)*a[i];
        s.push(i);
    }
    ll ans=0;
    int p;
    for(int i=1;i<=n;i++)
    {
        if(l[i]+r[i]-a[i]>ans)
        {
            ans=l[i]+r[i]-a[i];
            p=i;
        }
    }
    for(int i=p-1;i>0;i--)
    {
        if(a[i]>a[i+1])
            a[i]=a[i+1];
    }
    for(int i=p+1;i<=n;i++)
    {
        if(a[i]>a[i-1])
            a[i]=a[i-1];
    }
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}

那么对于这个算法的复杂度怎么计算?栈的复杂度看似不可测,实际上对于1~n中每个元素在整个for循环中都只会出入栈一次。那么整个程序就只涉及到常数倍的O(n),对于n=50000来说,时间复杂度是非常低的。题目的时限是3s,实际上这个程序只用了不到500ms。


小仙女