Largest Rectangle in a Histogram

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

8
4000

对于每个矩形，寻找它左边高度大于等于它的矩形，和右边大于等于它的矩形，记录下标。

#include"stdio.h"
#include"string.h"
#include"math.h"
#include"queue"
#include"vector"
#include"algorithm"
using namespace std;
#define N 100005
#define M 100000
#define LL __int64
#define min(a,b) (a<b?a:b)
LL h[N],l[N],r[N];
int main()
{
    int i,j,n;
    while(scanf("%d",&n),n)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%I64d",&h[i]);
        }
        h[0]=h[n+1]=-1;
        l[1]=1;
        r[n]=n;
        for(i=1;i<=n;i++)
        {
            int t=i;
            while(1)
            {
                if(h[t-1]>=h[i])
                    t=l[t-1];
                else
                    break;
            }
            l[i]=t;
        }
        for(i=n;i>=1;i--)
        {
            int t=i;
            while(1)
            {
                if(h[t+1]>=h[i])
                    t=r[t+1];
                else
                    break;
            }
            r[i]=t;
        }
        LL ans=0;
        for(i=1;i<=n;i++)
        {
            LL t=(r[i]-l[i]+1)*h[i];
            ans=ans>t?ans:t;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

hdu 1506 Largest Rectangle in a Histogram,布布扣,bubuko.com

hdu 1506 Largest Rectangle in a Histogram

原文：http://blog.csdn.net/u011721440/article/details/38496631