単調スタック

単調スタックを使うと、「左（または右）で最初に出てくる、自分より大きいもの」を全体 \(O(N)\) で求められる。
自分より小さいものは、自分の後ろに隠れて二度と答えにならないので捨ててよい。
だから、スタックの中身は常に単調（奥ほど大きい）になる。

• 各要素は \(1\) 回積まれ、捨てられるのも最大 \(1\) 回。while が何回回っても、全体の合計は \(O(N)\)。
• 処理の向きは、「先に確定する側」から。答えが左側で決まるなら左から、右側で決まるなら右から。
• スタックのトップを読む（ABC478 F）か、個数を読む（ABC372 D）かは問題による。
• 木の数え上げは、「各頂点の親の選び方」に言い換えると、掛け算で数えられることがある。
• 「最小値から取り出す」探索は、「待っている間に自分より大きいものが取り出されない」という条件に言い換えられる。
• まず遅い \(O(N^2) \) を書いて正しさを確かめ、内側のループだけをスタックに置き換えてもいい。

基本

イメージ：値を「身長」と考え、人が一列に並んでいく。新しく来た人は左を向いて、自分より背の高い人の中で一番近い人を探す。

• 自分より背の低い人は、自分の後ろに隠れる → 今後だれからも見つからないので捨てる
• 残った列は、左から右へ身長が下がっていく形になる（これが「単調」）

stack と vector のどちらでも書ける。速さはほぼ同じ。

慣れるまでは stack が意味をつかみやすい。
中身を全部出力してデバッグしたいときや、スタックの途中の要素を見たいときは vector にする。

コード例

左から 1 つずつ見て、自分より小さいものを捨て、残ったトップを読み、最後に自分を積む。

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

// res[i]：i より左で、a[i] より大きい最も近い要素の index（なければ -1）
vector<int> prev_greater(const vector<int>& a) {
    int n = a.size();
    vector<int> res(n, -1);
    stack<int> st;  // index を積む
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) st.pop();  // 隠れたものを捨てる
        res[i] = st.empty() ? -1 : st.top();                 // トップが答え
        st.push(i);                                          // 自分を積む
    }
    return res;
}

処理の向きの決め方（「うしろから考える」の基準）

判断の基準は「先に確定するのはどちら側か？」の 1 つだけ。 次の 2 つを自分に聞く。

• i の答えを決めるのに必要な情報は、i の前にある？うしろにある？
• 前から処理したら、何が「まだわからない」せいで困る？

うしろから考えるのがよく出てくる型

もう 1 つのコツ：「i+1 の答えを少し直すと、i の答えになる？」と考える。
ABC372 D は「真隣を足して、それより低いものを捨てる」だけで次の答えが作れる。