题目描述
链接：https://ac.nowcoder.com/acm/contest/1005/D
来源：牛客网

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.

分析
题目一看，我们要找最大的面积，先画一画，我们可以发现，当我们选择任何一个小直方图，它周围比他高的直方图我们都可以向它延伸，而当我们遇到第一个比它矮的，就不能再延伸了，所以说我们可以枚举每一个小直方图，然后构造r[N],l[N]两个数组，分别记录它向右向左可以延伸的最大距离，然后乘以它的高度，就可以求出它的面积了。

好，理论有了，动手实践。

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=1e5+10;
int n;
int h[N];
int p[N];//存储扫描到的小矩形序号
int l[N],r[N];
int tt;

signed main()
{
    while(scanf("%lld",&n)&&n)
    {
        for(int i=1;i<=n;i++)
            scanf("%lld",&h[i]);
        h[0]=h[n+1]=-1;//左右两边先构造一个负值，防止空栈 
        tt=-1;
        p[++tt]=0;
        for(int i=1;i<=n;i++)//向左边延伸 
        {
            while(h[p[tt]]>=h[i]) tt--;//遇到第一个比他矮的，就退出循环 
            l[i]=i-p[tt];//求宽度 
            p[++tt]=i;//记录矩形的序号 
        }
        tt=-1;
        p[++tt]=n+1;
        for(int i=n;i;i--)//向右边延伸 
        {
            while(h[p[tt]]>=h[i]) tt--;//遇到第一个比他矮的，就退出循环 
            r[i]=p[tt]-i;//求宽度 
            p[++tt]=i;//记录矩形的序号 
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            ans=max(ans,h[i]*(l[i]+r[i]-1));//高度乘宽度，求最大值 
        }
        cout<<ans<<endl;
    }
    return 0;
}