[競プロ] 単調スタック(Monotonic Stack)の説明

単調スタック(Monotonic Stack)とは

単調スタックという単語は勝手に作りました。
英語ではMonotonic Stackというらしいのですがそれに相当する日本語がなさそうだったのでそれっぽいものを勝手に使用。
定義は下記になります。

単調スタック:= スタックのある値がその下にある値よりも大きい
例：[5 4 3 2 1]
   top        bottom

実はこれは蟻本の「4-4 頻出テクニック２」の「スタックの利用」というセクションに説明されています。

なぜこれが便利なのか

これは主に配列Aにおいてある要素A[i]の値よりも前(j<i)にあるより小さい最初の値(A[j])を効率的に見つけるときに使われる

例えば、下記配列Aの4よりも前にある小さい値は3。
このようにある要素よりも前にあるより小さい要素のインデクスの配列をPとするとPは下記のようになる。（存在しない場合は-1とする）

配列A: [2  3 5 4  1]
配列P: [-1 0 1 1 -1]

この配列Pは下記の要領で単調スタックを利用して作成が可能。計算量はO(n)
説明が難しいのでコードを載せてコメントを記載
同じ要領である要素よりも後にある最初の小さい値も見つけることも可能

int n = A.size();
vector<int> P(n, 0);
stack<int> st; // 単調スタック。スタックには要素の値ではなくインデクスを格納する。
for (int i=0; i<n; i++) {
    // スタックの一番上の要素が今の要素よりも大きい限りpopして取り除く
    while (!st.empty() && A[st.top()] > A[i]) st.pop();
    // スタックが空の場合は今の要素より小さい要素が前にない
    if (st.empty()) P[i] = -1;
    // スタックの一番上の数は今の要素より小さい最初の前にある値
    else P[i] = st.top();
    st.push(i);
}

練習問題

907. Sum of Subarray Minimums
84. Largest Rectangle in Histogram
2281. Sum of Total Strength of Wizards