POJ 2559. Largest Rectangle in a Histogram

,

http://poj.org/problem?id=2559

ヒストグラム最大化というらしい。この手のstackの利用はよくあるしそういえば蟻本にも載っていたような気もする。 これを簡単に応用して、使ってはいけないマスが指定された上での最大の長方形の面積を$O(HW)$で求めるのも有名らしい。

solution

stackを使う。$O(N)$。

stackに高さを単調増加に持ちつつ、左から順に見ていく。 毎回stackを舐めて面積を計算すれば$O(N^2)$。 これは遅いので、長方形が伸びきる限界に来たときに一度だけ面積を計算するようにする。 つまりpopされる際に始めて面積を計算するようにし、これは$O(N)$。

implementation

#include <cstdio>
#include <stack>
// #include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
typedef long long ll;
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }

ll solve(int n, vector<int> const & h) {
    ll result = 0;
    stack<pair<int, int> > stk;
    repeat (i, n + 1) {
        int h_i = (i < n ? h[i] : 0);
        int j = i;
        while (not stk.empty() and stk.top().second > h_i) {
            // int h_j; tie(j, h_j) = stk.top();
            j = stk.top().first; int h_j = stk.top().second;
            stk.pop();
            setmax(result, h_j *(ll) (i - j));
        }
        if (stk.empty() or stk.top().second < h_i) {
            // stk.emplace(j, h_i);
            stk.push(make_pair(j, h_i));
        }
    }
    return result;
}

int main() {
    while (true) {
        int n; scanf("%d", &n);
        if (n == 0) break;
        vector<int> h(n); repeat (i, n) scanf("%d", &h[i]);
        ll result = solve(n, h);
        printf("%lld\n", result);
    }
    return 0;
}