撰写描述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.输入The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1<=n<=100000. Then follow nintegers h1,…,hn, where 0<=hi<=1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.输出For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.样例输入
7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0
样例输出
8 4000
提示Huge input, scanf is recommended.
题意：如图所示，在一个水面上有若干个矩形，求这些矩阵内部包含的最大矩形的面具。
题解：我们先假设矩形单调递增，那么从右往左累计的宽度乘当前高度就是所有可能的答案。
如果遇到一个不增的矩形进入，那么我们直接将前面部分高于该矩形的矩形直接按以上方法进行计算，再将高于新矩形的地方砍掉，即将这些矩形边计算边出栈，最后返回一个宽度为矩形宽度和，高度为新入栈矩形的高度的矩形入栈。
为什么可以这样？
假设在第i个矩形不增，那么第i个矩形之前的矩形都被计算过，第i个之后的矩形若是包含第i个，则高度不可能超过第i个，故所有情况都被考虑到了。
另外，输入很多，不建议用cin，并且输出的数爆int，用long long。
//#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
return b ? gcd(b, a%b) : a;
}
using namespace std;
const int maxn=1e5+10;
int a[maxn],s[maxn],w[maxn];
int main() {
int p,n;
ll ans=0;
while(cin>>n&&n) {
p=0,ans=0;
for(int i=1; i<=n; i++)scanf("%d", &a[i]);
a[n+1]=0,s[0]=0;
for(int i=1; i<=n+1; i++) {
if(a[i]>s[p]) {
s[++p]=a[i],w[p]=1;
} else {
int width=0;
while(s[p]>a[i]) {
width+=w[p];
ans=max(ans,(long long)width * s[p]);
p--;
}
s[++p]=a[i],w[p]=width+1;
}
}
cout<<ans<<endl;
}
return 0;
}