Largest Rectangle in Histgram

せっかくなんでブログの過去記事からひっぱってきた。
スタックにつむときに 2 パターンあるのがポイント
class largest_rectangle_in_histogram {
public:
    // 長方形の始点と終点を回る、素朴な2重ループでは O(N^2) で TLE してしまう。
    // stack を使った O(N) の解法を考える
    ll max_rectangle(const vector<ll> &_hist) {
        vector<ll> hist(_hist);
        stack<pair<int,ll>> st;

        ll maxArea = 0;
        // 最後のグラフも同じように扱いたいので、末尾に高さ 0 のダミーグラフをいれておく
        hist.push_back(0);
        REP(i, hist.size())
        {
            if (st.empty())
                st.emplace(i, hist[i]);
            else if (st.top().second == hist[i]) // 同じ高さが続くなら次へ
                continue;
            else
            {
                int prev = i;
                while ( st.size() && hist[i] < st.top().second )
                {
                    int l;
                    ll  h;
                    tie(l,h) = st.top();
                    st.pop();
                    prev = l;
                    maxArea = max(maxArea, (i-l)*h);
                }
                //
                // 上りで
                //
                //     |
                //   +-+
                //   |/
                // +-+/
                // |A B C
                //
                // B から長方形始まるケースとして (B,hist[B]) を登録するケース
                //
                //   +--+
                //   |  +-+
                // +-+    |
                // |......+-+
                //-+        |
                //  A BC D E
                // E からさかのぼって (A,hist[E]) を登録するケース
                //
                st.emplace(prev, hist[i]);
            }
        }
        return maxArea;
    }
    void solve(void) {
        while (true)
        {
            int N;
            cin>>N;
            if (N == 0)
                break;
            vector<ll> hist;
            REP(i, N)
            {
                ll h;
                cin>>h;
                hist.push_back(h);
            }
            cout<<max_rectangle(hist)<<endl;
        }
    }
};