単調スタック

単調スタックは、「片側で最も近い大きい値または小さい値」を、候補だけを残しながら1回の走査で求める手法です。このレッスンでは減少スタックを使い、各添字について右側で最初に現れる厳密に大きい値を求めます。時間計算量は O(n)、補助領域は最悪 O(n) です。

コードには入れ子の while がありますが、O(n²) にはなりません。各添字は一度だけ push され、最大一度だけ pop されます。全体では n 回の push と最大 n 回の pop、つまりスタック操作は 2n 回以下です。

単調スタックの仕組み

スタックには値だけでなく添字を保存します。添字があれば nums[index] で比較でき、答えが分かった瞬間に answer[index] へ書き込めます。

減少スタックは底から上へ非増加の値順を保ちます。nums[i] を調べるとき、現在値がスタック先頭より厳密に大きい間は pop を繰り返します。

while stack and nums[stack[-1]] < nums[i]:
    j = stack.pop()
    answer[j] = nums[i]
stack.append(i)

現在値が、pop された添字にとって「右側で最初」の大きい値だと言える理由は明確です。その添字は、push されてから現在位置までの途中で一度も pop されませんでした。つまり途中の値はどれも十分に大きくなく、現在値で初めて条件が成立したのです。

比較は厳密な < です。等しい値は「より大きい」ではないため、同じ値が複数スタックに残ることがあります。

単調スタックを使う場面

各位置で片側にある最も近い大きい値または小さい値を尋ねる問題が目印です。単調スタックを使うと、各位置から外側へ繰り返し探す処理を1回の走査へ置き換えられることがあります。

代表的な応用は次のとおりです。

• Daily Temperatures: 次に暖かい日までの距離を求める。
• Stock Span: 各価格について直前の大きい境界を求める。
• Largest Rectangle in Histogram: 各棒の左右で最も近い小さい境界を求める。

答えが一致した値だけではない場合は、添字を保存します。pop 時に書き込む内容を変えるだけで、同じスタックから値、添字、または距離を得られます。

単調スタックのステップ

初期入力は次です。

nums = [2, 1, 5, 3, 4]

答え配列は [-1, -1, -1, -1, -1] から始めます。右側に大きい値がない位置では、最後まで -1 が残ります。

1. i = 0、current = 2。 スタックは空なので添字 0 を push。値の並びは [2]。
2. i = 1、current = 1。 2 < 1 は偽なので pop せず、添字 1 を push。値は [2, 1]。
3. i = 2、current = 5。 先頭 1 は 5 より小さいため添字 1 を pop し、answer[1] = 5 と書きます。
4. 同じ current = 5 で新しい先頭 2 をもう一度比較します。2 < 5 も真なので添字 0 を pop し、answer[0] = 5 と書きます。
5. スタックが空になったので添字 2 を push。値は [5]。
6. i = 3、current = 3。 5 < 3 は偽。添字 3 を push して [5, 3]。
7. i = 4、current = 4。 3 < 4 は真。添字 3 を pop して answer[3] = 4。
8. 新しい先頭 5 は 4 より小さくないため終了し、添字 4 を push。値は [5, 4]。
9. 走査終了。添字 2 と 4 は右側に大きい値がないため -1 のままです。

最終結果は次です。

answer = [5, 5, -1, 4, -1]

アニメーションでは、成功したループ1回を compare → pop → resolve に分けています。スタックが変わる瞬間と答えを書き込む瞬間を別のビートにすることで、停止した各フレームが実際のアルゴリズム状態と一致します。

入れ子のループが O(n) である理由

for の中に while があっても、時間計算量は線形です。長さ n の入力では、各添字は自分の順番で必ず一度 push されるため、push はちょうど n 回です。

一度 pop された添字はスタックから永久に消え、二度目の pop はありません。したがって pop は最大 n 回です。

• pushes = n
• pops ≤ n
• pushes + pops ≤ 2n

1つの current が何回も pop を起こすことはあります。しかし、その pop は将来もう処理されない要素を消費しています。これが償却解析であり、個々の反復が高価でも全体の仕事量は線形です。

補助領域は最悪 O(n) です。[6, 5, 4, 3, 2, 1] のような厳密な減少列では走査中に pop が一度も起こらず、全添字がスタックに残ります。

境界ケース

厳密な増加列

[1, 2, 3, 4, 5] では、新しい値が毎回直前の先頭を pop します。結果は [2, 3, 4, 5, -1] で、スタックは浅いままです。

厳密な減少列

[5, 4, 3, 2, 1] では現在値が先頭より大きくならないため pop はゼロです。答えはすべて -1 で、スタック領域が最大になります。

重複値

[2, 2, 3] では2個目の 2 は1個目を pop しません。2 < 2 が偽だからです。3 が来ると2つの 2 が順に pop され、結果は [3, 3, -1] です。

右側に大きい値がない

最後までスタックに残る添字はエラーではありません。大きい値に出会わなかったので、初期値 -1 がそのまま正しい答えです。

よくある間違い

while を if に置き換える

最も重要な誤りです。スタック値が [2, 1]、current = 5 のとき、if 1回では 1 しか pop できません。値 2 の添字も 5 を答えにすべきなのに残ってしまいます。1つの current が複数の待機添字を解決できるため、繰り返しが必要です。

< を <= にする

「厳密に大きい」問題が「大きいまたは等しい」問題へ変わり、同値同士が誤って解決されます。

値だけを保存する

値だけでは比較はできますが、answer のどの位置へ書くか分かりません。添字を保存すれば値の参照と書き込み先の両方を持てます。

「厳密な減少スタック」と決めつける

ガードが厳密な < なので、等しい値は共存できます。正確な不変条件は「底から上へ非増加」です。

入れ子だから O(n²) と判断する

インデントではなく要素の寿命を数えます。各添字は一度入って最大一度出るだけです。最終画面の lifetime 行と work meter が、この償却された操作数をそのまま示します。