欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Largest Rectangle in a Histogram POJ - 2559(栈的运用)

程序员文章站 2022-05-22 15:05:34
...

传送门

题解:可以先看下CCF这个题:传送门

这种做法岂不是枚举么,如果确定了长方形的左端点L和右端点R,那么最大可能的高度就是min{hi|L<=i<R}。这样我们就得到了一个O(n^3)的算法。如果对计算区间最小值进行一些优化,那么复杂度可以将为O(N^2).但是即使这样,仍然无法在规定时间内求得答案。设面积最大的长方形的左端时L,右端是R,高度是H。如果h(L-1)>=H,那么左端点就可以更新为L-1,从而可以得到更大的长方形。这与假设矛盾,因此h(L-1)<H。同理可得h(R)<H,并且高度H=min{hi|L<=i<R}。因此,固定可以这样的H的i并进行分析。此时,L是满足h(j-1)<h(i)的最大的(j<=i)。R是满足h(j)<h(i)的最小的(j>i)。我们把两个值分别表示为L[I]和R[i]。如果能求出L[i]和R[i],那么最大的面积就是max{h(i)*(R[i]-L[i])。

用一个栈提前把L[i]和R[i]提前打好就好了

附上代码:


#include<iostream>
#include<cstdio>

using namespace std;

typedef long long ll;

const int maxn=1e5+50;

int n;
int h[maxn];
int l[maxn],r[maxn];
int st[maxn];

void solve()
{
    int t=0;
    for(int i=0;i<n;i++){
        while(t>0&&h[st[t-1]]>=h[i]){
            t--;
        }
        l[i]=t==0?0:(st[t-1]+1);
        st[t++]=i;
    }
    t=0;
    for(int i=n-1;i>=0;i--){
        while(t>0&&h[st[t-1]]>=h[i]){
            t--;
        }
        r[i]=t==0?n:st[t-1];
        st[t++]=i;
    }
    ll res=0;
    for(int i=0;i<n;i++){
        res=max(res,(long long)h[i]*(r[i]-l[i]));
    }
    printf("%lld\n",res);
}

int main()
{
    while(scanf("%d",&n)!=EOF&&n){
        for(int i=0;i<n;i++){
            scanf("%d",&h[i]);
        }
        solve();
    }
    return 0;
}

 

相关标签: stack