POJ 2559 Largest Rectangle in a Histogram（单调栈）

解题思路：

用单调栈求任意每个区间的最小值及区间长度，为什么记录区间最小值呢？(木桶装水原理，装水量取决于最短木板长)。枚举每个区间，维护最大答案。

//自行百度单调栈

AC代码：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<stack>
  4 
  5 using namespace std;
  6 
  7 stack<long long> le,ri;
  8 int n;
  9 struct kkk {
 10     long long v,l,r;
 11     long long xb;
 12 }a[100001];
 13 
 14 void chushihua() {
 15     for(int i = 1;i <= n; i++) {
 16         scanf("%lld",&a[i].v);
 17         a[i].xb = i;
 18     }
 19     while(!le.empty()) le.pop();
 20     while(!ri.empty()) ri.pop();
 21 }
 22 
 23 void left() {
 24     le.push(1);
 25     for(int i = 2;i <= n; i++) {
 26         if(le.empty()) {
 27             le.push(i);
 28             continue;
 29         }
 30         if(a[i].v >= a[le.top()].v) le.push(i);
 31         if(a[i].v < a[le.top()].v) {
 32             a[le.top()].r = i;
 33             le.pop();
 34             while(true) {
 35                 if(le.empty()) break;
 36                 if(a[le.top()].v > a[i].v) {
 37                     a[le.top()].r = i;
 38                     le.pop();
 39                 }
 40                 else break;
 41             }
 42             le.push(i);
 43         }
 44     }
 45     le.pop();
 46     a[n].r = n + 1;
 47     while(!le.empty()) {
 48         a[le.top()].r = n + 1;
 49         le.pop();
 50     }
 51 }
 52 
 53 void right() {
 54     ri.push(a[n].xb);
 55     for(int i = n - 1;i >= 1; i--) {
 56         if(ri.empty()) {
 57             ri.push(i);
 58             continue;
 59         }
 60         if(a[i].v >= a[ri.top()].v) ri.push(i);
 61         if(a[i].v < a[ri.top()].v) {
 62             a[ri.top()].l = i;
 63             ri.pop();
 64             while(true) {
 65                 if(ri.empty()) break;
 66                 if(a[ri.top()].v > a[i].v) {
 67                     a[ri.top()].l = i;
 68                     ri.pop();
 69                 }
 70                 else break;
 71             }
 72             ri.push(i);
 73         }
 74     }
 75     ri.pop();
 76     a[1].l = 0;
 77     while(!ri.empty()) {
 78         a[ri.top()].l = 0;
 79         ri.pop();
 80     }
 81 }
 82 
 83 long long answer() {
 84     long long ans = 0;
 85     for(int i = 1;i <= n; i++) {
 86         ans = max(ans,a[i].v * (a[i].r - a[i].l - 1));
 87     }
 88     return ans;
 89 }
 90 
 91 void tiaoshi() {
 92     for(int i = 1;i <= n; i++)
 93         cout << i << " " << a[i].l << " " << a[i].r << " " << a[i].v << endl;
 94 }
 95 
 96 int main() {
 97     while(true) {
 98         scanf("%d",&n);
 99         if(n == 0) return 0;
100         chushihua();
101         left();
102         right(); 
103         printf("%lld
",answer());
104     }
105     return 0;
106 }