Daily Temperatures
temperatures[i] は、i 日目の気温です。各日について、その日から厳密に気温の高い日が来るまで何日待つかを数えます。後の日に気温の高い日がない場合は 0 とします。同じ長さの配列を返し、i 番目の要素には i 日目の待ち日数を格納します。
関数
- temperaturesinteger-array
- 各日の気温を順番に
- 戻り値integer-array
- 各日について、より暖かい日までの日数。該当する日がない場合は0
制約
1 ≤ temperatures.length ≤ 10430 ≤ temperatures[i] ≤ 100- 「より暖かい」とは、気温が厳密に高いことを意味します。同じ気温の日が後に来ても該当しません。
例
- 入力
- temperatures = [71, 69, 72, 70, 70, 75, 68]
- 出力
- [2, 1, 3, 2, 1, 0, 0]
- 説明
- 0日目（71）は72を2日間待ちます。3日目（70）は4日目の同じ70を飛ばし、75を2日間待ちます。75または68の後にはそれより暖かい日がないため、どちらも0になります。
- 入力
- temperatures = [40, 50, 60]
- 出力
- [1, 1, 0]
- 説明
- 毎日、前日より暖かくなるため、最初の2日間はそれぞれ1日待ち、最後の日は0日です。
- 入力
- temperatures = [64, 60, 58, 61]
- 出力
- [0, 2, 1, 0]
- 説明
- 64 より後にそれ以上気温が高くなる日はないため、その後の日々で再び気温が上がるにもかかわらず、day 0 は 0 になります。60 の day 1 は、より低い 58 を飛ばし、61 になるまで 2 日待ちます。
発展問題
気温は30から100までの71種類の値しか取りません。気温をインデックスとするテーブルを使って、右から左へ一度走査するだけで毎日の答えを求めるにはどうすればよいでしょうか。また、そのコストはいくらでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
暖かい日がめったにない場合、毎日から先をスキャンすると、1日あたり最大10^4ステップかかることがあります。逆の方法を試しましょう。日付を左から右へ一度だけたどり、より暖かい日をまだ待っている日を保持します。暑い日が来たとき、それらの日はどうなるでしょうか？
待機日の気温は、最も古い日から最も新しい日に向かって上がることはありません。もし新しい日のほうが暖かければ、その日の時点ですでに古い日の答えが見つかっているはずです。したがって、待機日の中で最も寒いのは常に最も新しい日であり、スタックを使えばそれらをまさにその順序で保持できます。
日付のインデックスをスタックに保持します。新しい日ごとに、スタックの一番上の日の気温が今日より低い間、その日を取り出し、今日のインデックスからその日のインデックスを引いた値を答えとして保存します。その後、今日をスタックに追加します。最後にスタックに残った日には、0を保持します。
解説
毎日から順方向に走査すると作業が重複し、暖かい日が少ない場合は各走査が最後まで続きます。代わりに、日付を一度だけ順にたどり、新しい日がそれより前の、気温で上回る日々に答えを出すようにします。まだ答えを待っている日々は、下から上に向かって気温が上がらないスタックに置かれるため、すべての答えを一度の走査で得られます。
毎日、前方へスキャンする
正しいが、最大のテストでは終わらない
考え方
日 i について、日 i+1、i+2 などを確認し、初めて厳密に気温が高くなる日 j で停止します。答えは j-i です。走査が最後まで到達した場合は 0 です。順番に走査するので、最初に見つかる気温の高い日は、その中で最も近い日になります。
10^4 日すべてが同じ気温なら、走査が早期に停止することはありません。比較回数は約 n²/2 = 5 × 10^7 回となり、1 日目はすでに 0 日目がほぼ同じ範囲を走査したのに、もう一度ほぼ同じ範囲をたどります。
アルゴリズム
- 日数分の要素を持つ、すべて0の答えの配列を作成します。
- 各日
iについて、i+1から最終日までjを走査します。 temperatures[j] > temperatures[i]を満たす最初のjで、j-iを格納して走査を終了します。- 答えの配列を返します。走査で該当する日が見つからなかった日は0のままです。
def dailyTemperatures(temperatures):
n = len(temperatures)
answer = [0] * n
for i in range(n):
for j in range(i + 1, n):
if temperatures[j] > temperatures[i]:
answer[i] = j - i # the first warmer day, so stop here
break
return answer待機日数の単調スタック
考え方
まだ答えがない日を、インデックスとしてスタックに保持します。今日の日が来たら、今日より気温が低い待機中の日をすべてポップします。今日がその日より初めて暖かい日なので、その答えはtoday - dayです。その後、今日の日をプッシュします。
確認が必要なのはスタックの先頭だけです。気温がより低い上のすべての日がポップされた後にのみ、ある日がプッシュされるため、スタック上の気温は下から上に向かって上昇しません。今日の気温が先頭より高くなければ、その下にあるどの日よりも高くないので、ポップを止めます。最初の例では、5日目（75）が4日目、3日目、2日目をポップし、待機日数はそれぞれ1、2、3です。一方、2つ目の70は1つ目の70をポップしませんでした。同じ気温はより暖かいとはいえないためです。
各日は1回プッシュされ、ポップされるのは最大1回なので、ポップの合計は最大でもn回です。ある日が多くの日をポップすることがあっても、時間計算量はO(n)です。
アルゴリズム
- 0で初期化した答えの配列と、空のインデックスのスタックを作成します。
- 各日
todayについて、スタックの一番上の日の気温が今日より低い間、その日をスタックから取り出し、その日の答えをtodayからその日のインデックスを引いた値に設定します。 todayをスタックに追加します。- ループの後、スタックに残っている日はそれより暖かい日がないため、答えは0のままです。答えの配列を返します。
def dailyTemperatures(temperatures):
answer = [0] * len(temperatures)
waiting = [] # indices of days with no warmer day yet, colder toward the top
for today, temp in enumerate(temperatures):
# Today is the first warmer day for every colder day on top of the stack.
while waiting and temperatures[waiting[-1]] < temp:
day = waiting.pop()
answer[day] = today - day
waiting.append(today)
# Days still waiting never get a warmer day and keep their 0.
return answer
落とし穴と境界ケース
>=で取り出し、>を使わない。最初の例では、3日目は75のために2日待つ代わりに、2つ目の70のために1日待つことになります。- インデックスではなく気温をプッシュする。すると、距離を計算したり、答えのどの要素を埋めるべきか判断したりできません。
whileが必要なところでifを使う。暖かい日が1日あれば、待っている日をいくつも解決できます。最初の例では、75が3日分の答えになります。- スタックに残った日数の答えを未設定のままにする。答えは0です。Cでは、答えの領域を
callocで確保してください。mallocで確保したメモリには不定値が入っているためです。 - 前向きの走査を、最初に気温が上がる日を過ぎても続ける。
breakがないと、最後に気温が上がる日を記録してしまいます。
よくある質問3
Daily Temperatures の時間計算量はどれくらいですか？
単調スタックによる解法は、各日が1回プッシュされ、ポップされるのは最大1回であるため、時間計算量は O(n)、追加の空間計算量は O(n) です。各日から前方に走査すると、時間計算量は O(n²) となり、より暖かい日がない場合、10^4日で約5 × 10^7回の比較が必要です。
Daily Temperaturesはスタックを使わずに解けますか？
はい。最後の日から逆順に答えを埋め、日 i では j = i+1 から始めます。日 j の気温がより高くない間は、日 j の答えとなる日 j + answer[j] へジャンプします。answer[j] が 0 の場合、日 i の答えも 0 です。このジャンプによって、日 i の答えになり得ない日を飛ばせます。計算量は O(n) で、追加メモリは不要です。
Daily Temperatures は Next Greater Element とどのように関連していますか？
各位置について問われる内容は同じです。右側にある次のより大きな値を見つけます。Next Greater Element はその値を返し、Daily Temperatures はその値までの距離を返すため、スタックにはインデックスを格納します。同じスタックでも、より小さな値でポップするように反転させれば、次に小さい要素に関する問題に答えられます。
def dailyTemperatures(temperatures):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
temperatures = [71, 69, 72, 70, 70, 75, 68]
期待される出力
[2, 1, 3, 2, 1, 0, 0]