POJ 2559 Largest Rectangle in a Histogram ——————单调栈

àì夳堔傛蜴生んèń 2021-11-05 06:38 204阅读 0赞

# [POJ 2559 Largest Rectangle in a Histogram][] #

现在有  n n n 个宽度为  1 1 1 ，高度分别为 h 1 , h 2 , . . . , h n h\_1,h\_2,...,h\_n h1,h2,...,hn的长方形从左到右组成的柱状图。问里面包含的长方形的最大面积是多少？

下图对应的样例  
7  
2 1 4 5 1 3 3  
结果是 8 ，图中阴影部分  
![在这里插入图片描述][20190808165935237.gif]

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

用单调栈来维护以 h i h\_i hi为高度的矩阵块的左端点 L i L\_i Li和右端点 R i R\_i Ri;

对于一个单调递增栈来说，它具有向前延伸的性质。  
当要加入的元素之前有 n n n个栈元素出栈，那么说明这 n n n个出栈元素都会大于或者等于要入栈的元素。  
此时，我们需要维护入栈元素可以向前延伸多少个元素(相当于记录它的前面有多少个元素比它大)，  
而每个栈顶元素都要向出栈了的元素延伸，因为出栈了的元素一定是比它大的元素。  
就在 O ( n ) O(n) O(n)的时间复杂度内解决了上述问题…

我们正向维护单调递增栈的话，可以求得 L i L\_i Li  
我们逆向维护单调递增栈的话，可以求得 R i R\_i Ri

最后求一下  h i ∗ ( R i − L i ) h\_i\*(R\_i-L\_i) hi∗(Ri−Li) 的最大值就行了

/*--------- Hongjie ----------*/
    /**
     *　　　　　　　　┏┓　　　┏┓+ +
     *　　　　　　　┏┛┻━━━┛┻┓ + +
     *　　　　　　　┃　　　　　　　┃
     *　　　　　　　┃　　　━　　　┃ ++ + + +
     *　　　　　　 ████━████ ┃+
     *　　　　　　　┃　　　　　　　┃ +
     *　　　　　　　┃　　　┻　　　┃
     *　　　　　　　┃　　　　　　　┃ + +
     *　　　　　　　┗━┓　　　┏━┛
     *　　　　　　　　　┃　　　┃
     *　　　　　　　　　┃　　　┃ + + + +
     *　　　　　　　　　┃　　　┃　　　　Code is far away from bug with the animal protecting
     *　　　　　　　　　┃　　　┃ + 　　　　神兽保佑,代码无bug
     *　　　　　　　　　┃　　　┃
     *　　　　　　　　　┃　　　┃　　+
     *　　　　　　　　　┃　 　　┗━━━┓ + +
     *　　　　　　　　　┃ 　　　　　　　┣┓
     *　　　　　　　　　┃ 　　　　　　　┏┛
     *　　　　　　　　　┗┓┓┏━┳┓┏┛ + + + +
     *　　　　　　　　　　┃┫┫　┃┫┫
     *　　　　　　　　　　┗┻┛　┗┻┛+ + + +
     */
    
    // #include<bits/stdc++.h>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<deque>
    #include<cmath>
    #include<cstdio>
    #include<bitset>
    #include<string>
    #include<vector>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    typedef long long ll;
    typedef pair<int ,int> P;
    
    const int INF  = 0x3f3f3f3f;
    const int MAXN = 1e5+7;
    int n;
    int h[MAXN],L[MAXN],R[MAXN];
    int st[MAXN];
    
    int main(){
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            ios::sync_with_stdio(0);
            cin.tie(0);
            while(cin>>n&&n) {
        
                    for(int i=0;i<n;++i)
                            cin>>h[i];
                    stack<int> s;
                    for(int i=0;i<n;++i) {
        
                            while(!s.empty() && h[s.top()]>=h[i])
                                    s.pop();
                            L[i] = (int)s.size() == 0 ? 0 : s.top() + 1;
                            s.push(i);
                    }
                    while(!s.empty())
                            s.pop();
                    for(int i=n-1;i>=0;--i){
        
                            while(!s.empty() && h[s.top()]>=h[i])
                                    s.pop();
                            R[i] = (int)s.size() == 0 ? n : s.top();
                            s.push(i);
                    }
                    ll ans = 0;
                    for(int i=0;i<n;++i)
                            ans = max(ans, (ll)h[i]*(R[i] - L[i]));
                    cout<<ans<<endl;
              }
            return 0;
    }

[POJ 2559 Largest Rectangle in a Histogram]: http://poj.org/problem?id=2559
[20190808165935237.gif]: /images/20211104/295208bef42a48e4aeb813b962258d46.png