単調スタック
01 / 一文での本質
値が単調に保たれるスタックを維持する —— 次の要素が順序を破るたびに、ポップされる要素は まさに「現在の要素が答えとなる」要素である。
問題添字ごとの次に大きい要素入力[2, 1, 2, 4, 3, 1]
入力
20
11
22
43
34
15
スタック →
— 空 —
結果
?0
?1
?2
?3
?4
?5
左から右へ走査する。値が下から上へ厳密に減少する添字のスタックを保つ。
ステップ
0 / 16
i
—
スタック長
0
結果の充填
0 / 6
0 / 16
02 / パターンの骨格
# 次に大きい要素 —— 厳密減少のスタックstack ← [ ]for i in 0..n−1:while stack が空でなく かつ arr[stack.top] < arr[i]:j ← stack.pop()result[j] ← arr[i] // i が j の次に大きい要素stack.push(i)# スタックに残った要素は右側に大きい要素がない → result ← −1
03 / このパターンを使うべき合図
「次に大きい / 小さい」
各要素について、その右(または左)で最も近い大きい(または小さい)要素を求める。 このパターンは違反者が現れた瞬間に、その添字の答えを出力する。
「各要素について…を求めよ」
答えは添字ごと、集約値ではない ——そして関係は位置に基づくものであり、値そのものに基づくものではない。
「ヒストグラム / span」
最大長方形、雨水捕集、株価スパン —— いずれも、最も近い大きい / 小さい近傍が境界を定める問題。
「O(n)」
目標計算量からして、添字ごとに O(N²) の素朴な走査は除外され、 償却 1 パスのアプローチが暗示されている。
04 / よくある落とし穴
i.
値ではなく添字を積むべきところを取り違える。
ポップ時にはほぼ必ず
result[j] に書き込むので、スタックは 各ポップ要素がどこから来たかを覚えていなければならない。 添字を積み、値は arr[stack.top] で参照する。ii.
内側 while における
< と ≤。厳密(
<)は「厳密に次に大きい」—— 同値はより大きいものが来るまでスタックに残る。 非厳密(≤)は「次に同じか大きい」—— 同値もポップされ、互いに答えを記録する。 これらは別問題であり、選択が同値ケースの結果を静かに変えてしまう。iii.
末尾の残りを忘れる。
ループ終了時にスタックに残っている添字には、右側に「より大きい要素が存在しない」。 結果を
-1 に初期化する(あるいは仕様に応じてスキップする)。 見落としやすい部分だ。05 / LeetCode で練習
難易度順に 4 問。最初の 2 問は next-greater のウォームアップ、 後ろの 2 問は単調スタックが真価を発揮する問題。