スタックで今日より暖かい日まで何日待つかを並べる

スタック問題 105

毎日の気温の並びから、日ごとに「今日より暖かい日が来るまで何日待つか」を並べます。まだ答えの決まらない日をスタックに積み、暖かい日が来たらまとめて答えを決める、単調スタックの練習です。

海外で定番の問題リスト 4 本には入っていません

問題

毎日の最高気温を、日の順に整数の並び temps で受け取ります。日ごとに、その日より後で、その日より気温が高い最初の日まで何日あるかを並べて返す関数を書いてください。

返す並びの i 番目は、i 日目より後で temps[i] より高い気温の最初の日を j 日目としたときの j - i です
そういう日が無ければ 0 にします。同じ気温の日は、暖かい日と数えません
temps の長さは 1 以上 100000 以下で、値は -50 以上 50 以下です

入力と出力の例

例 1

1 日目の 18 度より暖かいのは、3 日後の 21 度が最初です。21 度の日は、2 日後の 22 度まで待ちます。最後の日は後ろに日が無いので 0 です。

temps = [18, 16, 17, 21, 19, 22]

[3, 1, 1, 2, 1, 0]

例 2

毎日下がっていくので、どの日も暖かい日は来ません。

temps = [25, 24, 23]

[0, 0, 0]

例 3

同じ気温は暖かい日と数えません。1 日目の 20 度は、2 日目の 20 度を飛ばして 3 日目の 21 度まで待ちます。

temps = [20, 20, 21]

[2, 1, 0]

面接での聞かれ方

面接では、気温の言葉のまま渡されることがよくあります。

「毎日の気温から、より暖かい日まで何日待つかを返してください」
「同じ気温は暖かいと数えますか？」と、自分から確かめるかを見られます
書き終えたあとに「同じ考えで解ける問題をほかに知っていますか？」と聞かれることもあります

「次に大きい値」を探す問題は、株価、建物の見晴らし、ヒストグラムなど、形を変えてよく出ます。単調スタックという名前とあわせて覚えておくと、話を広げられます。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「スタックとキュー」に、この型の要点を表とコードでまとめています。

スタックは後から入れた物を先に、キューは先に入れた物を先に取り出します。括弧の対応や、順番待ちの処理の形です。

まず考える手順

段 1

素直に書くなら、日ごとに後ろの日を順に見て、最初に高い日を探します。正しく動きますが、下がり続ける並びでは日ごとに最後まで見るので O(n²) です。長さ 10 万では遅すぎます。

段 2

見方を変えて、前から 1 日ずつ読みながら「まだ暖かい日が来ていない日」を覚えておきます。新しい日の気温が、覚えている日の気温より高ければ、その日の答えはここで決まります。

段 3

答えの決まらない日の気温は、後ろほど低いか同じに並びます。高い日が来たら前の低い日は決まってしまうので、残るのは下がっていく並びだけだからです。そこで、答えの決まらない日をスタックに積みます。新しい日が来たら、スタックの上の日の気温が新しい日より低いあいだ取り出して、その日の答えを「新しい日 − その日」に決めます。最後に新しい日を積みます。

段 4

スタックには、気温ではなく日の番号を積みます。答えは日の差で、気温は番号から読めるからです。最後までスタックに残った日は暖かい日が来なかった日で、答えは初めに入れた 0 のままにします。

解答

Python

def days_until_warmer(temps):
    ans = [0] * len(temps)
    stack = []
    for i in range(len(temps)):
        t = temps[i]
        while stack:
            j = stack[-1]
            if temps[j] >= t:
                break
            stack.pop()
            ans[j] = i - j
        stack.append(i)
    return ans

JavaScript

function daysUntilWarmer(
  temps
) {
  const n = temps.length;
  const ans = Array(n).fill(0);
  const stack = [];
  for (let i = 0; i < n; i++) {
    const t = temps[i];
    while (stack.length > 0) {
      const j = stack.at(-1);
      if (temps[j] >= t) break;
      stack.pop();
      ans[j] = i - j;
    }
    stack.push(i);
  }
  return ans;
}

Go

func daysUntilWarmer(
	temps []int,
) []int {
	ans := make([]int, len(temps))
	stack := []int{}
	for i, t := range temps {
		for len(stack) > 0 {
			top := len(stack) - 1
			j := stack[top]
			if temps[j] >= t {
				break
			}
			stack = stack[:top]
			ans[j] = i - j
		}
		stack = append(stack, i)
	}
	return ans
}

stack には、まだ答えの決まらない日の番号が積まれています。上の日の気温が新しい気温 t 以上なら、その下の日はもっと高いか同じなので、そこで止めてかまいません。条件を >= にしているので、同じ気温では取り出さず、例 3 の決まりを守れます。

計算量

時間は O(n) です。どの日も、積まれるのが 1 回、取り出されるのが多くて 1 回です。取り出す繰り返しも、全体で n 回を越えません
使う記憶は O(n) です。下がり続ける並びでは、全部の日がスタックに残ります。答えの並びは数えていません
段 1 の後ろを順に見る書き方は、時間が O(n²) です

よくある間違い

同じ気温でも取り出す。条件を > ではなく >= で止めないと、例 3 の 1 日目の答えが 1 になります。同じ気温は暖かい日ではありません
スタックに気温を積む。答えに要るのは日の差なので、気温だけでは答えを書けません。番号を積み、気温は並びから読みます
答えを日の番号 j のまま入れる。求めるのは待つ日数なので、i - j です
残った日の答えを -1 にする。暖かい日が来ないときは 0 です。最初に 0 で埋めておけば、何もしなくて済みます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def days_until_warmer(temps: list[int]) -> list[int]:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(days_until_warmer([18, 16, 17, 21, 19, 22]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します