POJ 2559: Largest Rectangle in a Histogram

蟻本めぐりです。4-4 は本当に全然読んでないことがわかりました。

問題

2559 -- Largest Rectangle in a Histogram

n 個の幅 1, 高さ h1, h2, ..., hn の長方形が順番に並んでいる。この中に含まれる長方形の面積の最大値を求めよ。

解法

よくあるスタックのテクニックで解けるんですが, 蟻本の書き方が結構わかりやすい気がするのでこれから stack を陽に使わないような形で書きたいと思います…

ある座標 i の長方形が最小であるとすると, h[j] >= h[i] (j <= i) を満たす間はなるべく左に行き, 同様に h[j] >= h[i] (j >= i) を満たす間はなるべく右に行くほうが良いです。この境界ラインである j を求めるためにスタックを使います。
スタック st に h[i] > h[st[k]] を満たす可能性のある要素だけを残しておくようにして, st を増減させていけば良いです。

const int MAXN = 100010;
ll h[MAXN], w[MAXN];
int n, st[MAXN];

int main() {
    while (cin >> n) {
        if (n==0) break;
        memset(w, 0, sizeof(w));
        for (int i = 0; i < n; i++) scanf("%lld", h+i);
        int t = 0;
        for (int i = 0; i < n; i++) {
            while (t > 0 && h[st[t-1]] >= h[i]) t--;
            w[i] += (t==0 ? i+1 : i-st[t-1]);
            st[t++] = i;
        }
        t = 0;
        for (int i = n-1; i >= 0; i--) {
            while (t > 0 && h[st[t-1]] >= h[i]) t--;
            w[i] += (t==0 ? n-i : st[t-1]-i);
            st[t++] = i;
        }
        ll ans = 0;
        for (int i = 0; i < n; i++) ans = max(ans, h[i]*(w[i]-1));
        printf("%lld\n", ans);
    }
    return 0;
}