POJ 2559 Largest Rectangle in a Histogram(单调栈)解题报告

2017-04-06 2,668 次浏览 解题报告

解题思路

单调栈的基础应用。我们以矩形高度为单位建立一个单调不降的栈,每次输入一个新的矩形高度 h 时,如果新的高度比栈顶高度低,则一直 pop,并累计 pop 出的元素的宽度,每次 pop 我们都可以看做得到一个高度为 h,宽度为累计总宽度的一个矩形(可以看做是把这段的所有矩形高度都削减为 h),用它的面积更新答案。pop 结束后将我们最终得到的新矩形入栈即可。

参考代码

#include <cstdio>
#include <stack>
using namespace std;

struct info {
    int h, w;
};

int main(int argc, char const *argv[]) {
    int n, h;
    while(scanf("%d", &n), n) {
        stack<info> s;
        long long ans = 0;
        for(int i=0; i<n; ++i) {
            scanf("%d", &h);
            int w = 0;
            while(!s.empty() && s.top().h>h) {
                w += s.top().w;
                ans = max(ans, 1LL*s.top().h*w);
                s.pop();
            }
            s.push((info){h, w+1});
        }
        int w = 0;
        while(!s.empty() ) {
            w += s.top().w;
            ans = max(ans, 1LL*s.top().h*w);
            s.pop();
        }
        printf("%lld\n", ans);
    }
    
    return 0;
}

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2017/04/06/poj-2559.dream

还不快抢沙发

添加新评论