SP1805 HISTOGRA

---------------------------------------------------

我就是想学个单调栈然后全网都是个蓝题

---------------------------------------------------

连接：

POJ

洛谷

---------------------------------------------------

（字都在注释上）

 1 #include<iostream>
 2 #include<stack>
 3 #include<cstdio>
 4 #include<cstring>
 5 using namespace std;
 6 struct s{
 7     long long w;
 8     long long h;
 9 };
10 long long high[100100];
11 stack <s>st;
12 long long n;
13 long long deal(){
14     long long ans=0;
15     s now;
16     now.w=0;
17     now.h=0;
18     st.push(now);//初始化 
19     for(long long i=1;i<=n+1;++i){  //n+1是因为n+1是个零，所以说可以清空栈 
20             long long nw=0;
21         if(high[i]>st.top().h)//我们要维护的是一个递增的 
22         {
23             now.w=1;
24             now.h=high[i];
25             st.push(now);
26         }
27         else
28         {
29         
30             while(st.top().h>high[i]){//单调栈的特性，一直弹出栈顶 
31                 nw+=(st.top()).w;//计算宽度的和 
32                 ans=max(ans,1ll*nw*st.top().h);//计算高 
33                 st.pop();
34             }
35             //这些弹出来的矩形不能扔，要和后面的合并 
36                 st.push((s){nw+1,high[i]});//合并后放入 
37         }
38     
39     }
40     return ans;
41 }
42 long long main(){
43     while(scanf("%lld",&n)&&n){    //poj就这样，要读入多个数据 
44         for(long long i=1;i<=n;++i){
45             scanf("%lld",&high[i]);
46         }
47         prlong longf("%lld
",deal());
48         memset(high,0,sizeof(high));//记得清零，我因为没清零wa了qwq 
49     }
50     return 0;
51 }