poj 2559 单调栈 ***

给出一系列的1*h的矩形，求矩形的最大面积。
如图：
题解链接：点我
 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<iostream>
 6 using namespace std;
 7 const int MAXN=100005;
 8 pair<int,int> ele[MAXN];
 9 int main(){
10     int height, n;
11     int w;
12     int i,j,k;
13     long long ans, tot, tmp;
14     int top=0;
15     #ifndef ONLINE_JUDGE
16     freopen("1.txt","r",stdin);
17     #endif
18     while (scanf("%d", &n) != EOF && n)
19     {
20         top = 0;
21         ans = 0;
22         for(i=0;i<n;i++){
23             tmp=0;
24             scanf("%d",&w);
25             while(top>0&&w<ele[top-1].first){
26                 long long aans=(long long)ele[top-1].first*(ele[top-1].second+tmp);
27                 ans=max(ans,aans);
28                 tmp+=ele[top-1].second; //这个比较容易忘，这是当前累计的加上之前累计的
29                 top--;
30             }
31             ele[top].first=w;
32             ele[top].second=1+tmp;
33             top++;
34         }
35         tmp=0;
36         while(top>0){
37                 long long aans=ele[top-1].first*(ele[top-1].second+tmp);
38                 ans=max(ans,aans);
39                 tmp+=ele[top-1].second;
40                 top--;
41         }
42         printf("%lld
", ans);
43 
44 
45     }
46     return 0;
47 
48 }