地面上从左到右并排紧挨着摆放多个矩形，已知这此矩形的底边宽度都为1，高度不完全相等。求在这些矩形包括的范围内能得到的面积最大的矩形，打印出该面积。所求矩形可以横跨多个矩形，但不能超出原有矩形所确定的范围。
如 n = 7, 序列为2 1 4 5 1 3 3
_ _
_ | | _ | |
| || | _ _ |H||H| _ _
_ | || | | || | _ |H||H| | || |
| | _ | || | _ | || | | | _ |H||H| _ | || |
|_||_||_||_||_||_||_| |_||_||H||H||_||_||_| 最大面积：8
输入有多组数据，每组数据一行：
第一个数N，表示矩形个数
后面跟N个正整数，第i个正整数hi表示第i个矩形的高度。
最后一行，以一个单独的0结束。
每组输入数据一行，一个数表示最大矩形面积。
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
08
4000时间：1s 空间：64M
30 %: 1<=N<=100
60 %: 1<=N<=1,000
100%: 1<=N<=500,000，0<=hi<=1,000,000,000
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
long long n,h[1000001],q[1000001],p[1000001],ans,top=1,tmp,now;
int main(){
scanf("%lld",&n);
while(n!=0){
top=1;
ans=0;
for(int i=1;i<=n;i++){
scanf("%lld",&h[i]);
}
n+=1;
for(int i=1;i<=n;i++){
now=i;
while(h[i]<q[top-1]){
tmp=(i-p[top-1])*q[top-1];
now=p[top-1];
ans=max(ans,tmp);
top--;
}
if(h[i]>q[top-1]){
q[top]=h[i];
p[top]=now;
top++;
}
}
printf("%lld\n",ans);
scanf("%lld",&n);
}
return 0;
}
原文：https://www.cnblogs.com/xiongchongwen/p/11192379.html