【题目描述】：
地面上从左到右并排紧挨着摆放多个矩形，已知这此矩形的底边宽度都为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
0【样例输出】：
8
4000【时间限制、数据范围及描述】：
时间：1s 空间：64M
30 %: 1<=N<=100
60 %: 1<=N<=1,000
100%: 1<=N<=500,000，0<=hi<=1,000,000,000
题解：单调栈，本题算模板题目吧……但本蒟蒻不是很懂QAQ
#include<bits/stdc++.h> #include<iostream> #include<algorithm> #include<queue> #include<cmath> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; typedef long long ll; const int N=500005; stack<int>s; int n,x; ll a[N],m,ans,r[N],l[N]; int main(){ freopen("48.in","r",stdin); freopen("48.out","w",stdout); while(1){ scanf("%d",&n); if(n==0) break; ans=0; a[0]=-1;a[n+1]=-1; for(int i=1;i<=n;i++) scanf("%lld",&a[i]); while(!s.empty()) s.pop(); s.push(0); for(int i=1;i<=n;i++){ for(x=s.top();a[x]>=a[i];x=s.top()) s.pop(); l[i]=x+1; s.push(i); } while(!s.empty()) s.pop();s.push(n+1); for(int i=n;i>0;i--){ for(x=s.top();a[x]>=a[i];x=s.top()) s.pop(); r[i]=x-1; s.push(i); if((r[i]-l[i]+1)*a[i]>ans) ans=(r[i]-l[i]+1)*a[i]; } printf("%lld ",ans); } return 0; }