Donutsプロコンチャレンジ2015 C - 行列のできるドーナツ屋 (1Q)

スタックの応用問題！　ヒストグラムの最大長方形を求めるアルゴリズムと似たようなスタックの使い方をする！

• 問題へのリンク

問題概要

長さ の数列 が与えられる。これらの値は互いに相異なる。

各 に対して、次の条件を満たす整数 の個数を求めよ。

• 
• なる任意の に対して、 である

制約

• 

考えたこと

この手のものはスタックで解けると相場は決まっている。類題として次の問題がある。

drken1215.hatenablog.com

• 数列を前から順にスタックに挿入していき、
• 毎回、その時点でのスタックのサイズを出力して、
• 新たな要素を挿入する前に、その要素以下の値はすべて pop して、
• 新たな要素を挿入する

というようにすれば OK。計算量は 。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, H;
    cin >> N;
    vector<int> st;
    for (int i = 0; i < N; i++) {
        cout << st.size() << endl;

        cin >> H;
        while (!st.empty() && st.back() <= H) st.pop_back();
        st.push_back(H);
    }
}