「明日は半袖でいい?」

天気アプリを作るとしましょう。ユーザーが知りたいのは意外とシンプルです。「今日より暑い日はいつ来る?」

これから数日間の予想気温が与えられたとき、各日についてその日より初めて暑くなる日が何日後かを知らせたい。暑い日が最後まで来なければ0です。

例: 気温が [23, 24, 22, 21, 25, 28, 26] なら答えは [1, 3, 2, 1, 1, 0, 0]。
Day 1(24°)は3日後のDay 4(25°)で初めて暑くなり、Day 5(28°)は後ろに暑い日がなく0。

最初に思いつく解法 (そしてその限界)

直感的にはこう解きます。各日について右側を最後まで走査して暑い日を探すのです。

for 各日 i:
    for j = i+1 .. 末尾:
        if temps[j] > temps[i]: 答え = j - i; break

小さい入力では動きます。でも日数が10万個なら? 10万 × 10万 = 100億 回の比較 → 時間切れ。二重ループのO(n²)はコーディングテストで頻繁に足を引っ張ります。

ここで発想を変えましょう。各日を 「答えを待つ客」 だと考えてみてください。

•Day 0 (23°): 「いつ私より暑くなる?」→ まだ分からない。とりあえず列(スタック)に並んで待機。
•Day 1 (24°) 登場: あれ、24 > 23! Day 0の答えがすぐに見つかった(1日後)→ Day 0は列から退場。
•Day 2 (22°)、Day 3 (21°): どんどん寒くなるので誰も答えを見つけられず列が伸びます。
•Day 4 (25°) 登場: 25 は列で待っていた 21 → 22 → 24 を近い順に一気に追い抜く! 3つが同時に答えを見つけて退場します。

気づきましたか? 最も最近並んだ人が最初に抜けます。 これはまさにスタック(LIFO)の動きです。

そして列に残る気温を見ると、常に降順です(24 → 22 → 21)。この *単調性* を保つスタックを単調スタック(Monotonic Stack)と呼びます。

単調スタックが速い理由は明快です。

だから総演算回数は 2n を超えません。つまり O(n)。二重ループの100億回が10万回程度に減ります。

このパターンは「次に大きい数」「右側で最も近い〜」「株価が下がる直前」など無数の変形でコーディングテストに登場します。一度原理を身につければ、服を着替えただけの問題が全部同じに見えてきます。

気温の棒が並び、答えのない日がスタックに積まれ、暑い日が現れた瞬間に連鎖的にpopされて答えが埋まる全工程をステップ別の可視化で用意しました。スタックの変化・答え配列が埋まる様子まで一目で分かります。