大佬讲解：http://blog.csdn.net/dgq8211/article/details/7740610
http://blog.csdn.net/u013491262/article/details/22900261
这个图形从左到右由若干个 宽为1 高不确定 的小矩形构成，求出这个图形所包含的最大矩形面积。
多组测试数据 每组测试数据的第一行为n(1 <= n <= 100000)， 表示图形有n个小矩形构成. 接下来一行输入n个整数h1, h2...hn (0 <= hi <= 1000000000, 1 <= i <= n), 表示每个小矩形的高度 n为0时程序结束
仅输出一行表示面积的最大值
7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0
8 4000
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
int q[maxn] = {-1}, w[maxn];
int main()
{int n, h;while(scanf("%d", &n), n){int top = 0;ll ans = 0;for(int i = 1; i <= n+1; i++){if(i != n+1) scanf("%d", &h);else h = 0;if(h > q[top])q[++top] = h, w[top] = 1;else{ll cnt = 0;while(h <= q[top]){ans = max(ans, (cnt + w[top]) * q[top]);cnt += w[top--];}q[++top] = h;w[top] = cnt + 1;}}printf("%I64d\n", ans);}return 0;
}