Histogram Largest Rectangle (ヒストグラムの最大長方形)
(dp/histogram_largest_rectangle.hpp)

• View this file on GitHub
• Last update: 2023-02-06 19:40:21+09:00
• Include: #include "dp/histogram_largest_rectangle.hpp"

• ヒストグラムの最大長方形を求める
• $ O(N) $

お気持ち

• 高さを $ h_i $ と決め打つと、左右に広げるイメージで、左側で初めて $ h_i > h_j $ となる $ j $ と、右側で初めて $ h_i > h_j $ となる $ j $ の両方が求められれば良い。前者について考えることにする。
• $ i=0,1,2,… $ の順 (昇順) に計算しているとする。$ i $ の計算が終わり、$ i+1 $ の計算を行う場合、$ 0,1,…,i $ が $ j $ の候補となるのだが (※いずれも $ j $ とならない場合もある)、実際には $j=i,i-1,i-2,…,0 $ の順 (降順) で見たときに、それまでに見ていた $ h_j $ と $ h_{i+1} $ の最小値を更新した添字のみが候補になる。(そうでない添字が選ばれるとしたら、もっと早い段階で $ h_i > h_j $ となる $ j $ が出てきているはずである)
• しかもここで候補となっていない添字は $i+2,i+3,…,n-1$ に対する計算でも出てくることがない。(最小値を更新する、という条件が、$h_{i+2}, h_{i+3},…$ の登場によりどんどん厳しくなるだけなため)
• よってこの候補をスタックで管理すれば良い
• 後者については $ i $ の降順に計算すれば同じようにできる

Verified with

• verify/aoj_dpl/aoj_dpl_3_c.test.cpp

Code

#pragma once

template <class T> T histogram_largest_rectangle(std::vector<T> &h) {
    int n = (int)h.size();
    std::vector<int> st(n), L(n), R(n);
    int t = 0;
    for (int i = 0; i < n; i++) {
        while (t > 0 and h[st[t - 1]] >= h[i]) t--;
        L[i] = (t == 0 ? 0 : st[t - 1] + 1);
        st[t++] = i;
    }
    t = 0;
    for (int i = n - 1; i >= 0; i--) {
        while (t > 0 and h[st[t - 1]] >= h[i]) t--;
        R[i] = (t == 0 ? n : st[t - 1]);
        st[t++] = i;
    }
    T res = 0;
    for (int i = 0; i < n; i++) res = std::max(res, h[i] * (R[i] - L[i]));
    return res;
}

#line 2 "dp/histogram_largest_rectangle.hpp"

template <class T> T histogram_largest_rectangle(std::vector<T> &h) {
    int n = (int)h.size();
    std::vector<int> st(n), L(n), R(n);
    int t = 0;
    for (int i = 0; i < n; i++) {
        while (t > 0 and h[st[t - 1]] >= h[i]) t--;
        L[i] = (t == 0 ? 0 : st[t - 1] + 1);
        st[t++] = i;
    }
    t = 0;
    for (int i = n - 1; i >= 0; i--) {
        while (t > 0 and h[st[t - 1]] >= h[i]) t--;
        R[i] = (t == 0 ? n : st[t - 1]);
        st[t++] = i;
    }
    T res = 0;
    for (int i = 0; i < n; i++) res = std::max(res, h[i] * (R[i] - L[i]));
    return res;
}

Back to top page