POJ2559 Largest Rectangle in a Histogram

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<stack>
 4 #include<cctype>
 5 using namespace std;
 6 inline void read(int &tmp)
 7 {
 8     int x=1;char c=getchar();
 9     for(tmp=0;!isdigit(c);c=getchar()) if(c=='-') x=-1;
10     for(;isdigit(c);tmp=tmp*10+c-48,c=getchar());
11     tmp*=x;
12 }
13 typedef pair<int,int> PAIR;//first--高 second--宽 
14 stack<PAIR> q;
15 int n;
16 int main()
17 {
18     read(n);
19     while(n)
20     {
21         long long ans=0;//不开long long见祖宗 
22         for(int i=1,tmp;i<=n+1;i++)
23         {
24             if(i<=n) read(tmp);
25             else tmp=0;//避免栈内有剩余矩形 
26             if(q.empty()||tmp>q.top().first)//维护单调递增栈 
27             {q.push(make_pair(tmp,1));continue;}
28             int tot=0;
29             while(!q.empty()&&tmp<q.top().first)
30             {
31                 tot+=q.top().second;
32                 ans=max(ans,(long long)q.top().first*tot);
33                 q.pop();
34             }
35             q.push(make_pair(tmp,tot+1));//该矩形前已考虑过，直接把高度为当前矩形高度、宽度为累计宽度+当前宽度(1)的矩形入栈 
36         }
37         printf("%lld
",ans);
38         read(n);
39     }
40     return 0;
41 }