定義

単調スタックは、要素(通常はインデックス)が常に増加または減少の順序を保つように管理されるスタックです。「次に大きい要素」問題では、スタックに積まれた値が上に行くほど小さくなる(単調減少)状態を保ちながらインデックスを積みます。

主な特性

• ✓値ではなく「インデックス」をスタックに保存 - 後でどの位置に答えを埋めるか分かるため
• ✓スタック頂上の値より大きい新しい値が来ると、pop しながら答えを埋める - その要素の次に大きい要素を見つけたということ
• ✓各インデックスはちょうど一度 push され、最大一度 pop される - だから全体で O(n)
• ✓最後まで pop されず残ったインデックスは次に大きい要素がない - 答えは -1

時間計算量