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で、最初に気温が高くなるのは2日目の72なので、2日待ちます。3日目と4日目はどちらも70です。2回目の70は気温が高くないため、3日目は5日目の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以降にそれより暖かい日がないため、その後の日が再び暖かくなっても、0日目は0になります。60度の1日目は、より寒い58度の日を飛ばし、61度になるまで2日間待ちます。
提出時に隠しテスト+13件
発展問題
温度は30から100までの71種類の値しか取りません。温度をインデックスとするテーブルを使って、右から左への1回の走査ですべての日に答えるにはどうすればよいでしょうか。また、その走査の計算量はいくらでしょうか。
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
暖かい日がめったにない場合、毎日から先へ走査すると、1日あたり最大10^4ステップかかることがあります。逆に考えてみましょう。日を左から右へ一度だけたどり、より暖かい日をまだ待っている日を記録しておきます。暑い日が来たら、それらの日には何が起こるでしょうか？
待機日数は古い日から新しい日へ進むにつれて、暖かくなることはありません。もし新しい日のほうが暖かければ、その日の時点ですでに古い日の答えが見つかっているはずです。したがって、待機中の日のうち最も寒いのは常に最も最近の日であり、スタックはそれらをまさにその順序で保持します。
- 日付のインデックスをスタックに保持します。新しい日ごとに、スタックの一番上の日が今日より寒い間、それを取り出し、今日のインデックスからそのインデックスを引いた値を答えとして保存します。その後、今日を追加します。最後にスタックに残っている日には、0を保持します。
解説
1日分なら答えは前方への走査で求められますが、すべての日について走査すると同じ作業を繰り返し、暖かい日がまれな場合は各走査で配列の末尾まで進みます。解決策は、後の日について尋ねるのではなく、各日がそれより前の日に答えるようにすることです。まだ答えを待っているインデックスを積み、気温順に並べておけば、1回の走査ですべての答えを求められます。
毎日、先へとスキャンする
正しいが、最大のテストでは終わらない
考え方
問題文の指示どおりにします。日 i について、日 i+1、次に i+2 と順に調べ、気温が厳密に高い最初の日で止めます。距離 j-i が答えです。見つからないまま最後まで到達した場合、答えは 0 のままです。
後の日を順番に調べるため、最初に見つかる気温の高い日は、実際に存在する最初の気温の高い日です。そこで止めることも重要です。調べ続けると、最後に見つかった気温の高い日を記録してしまいます。
気温の高い日が遠くにある場合や存在しない場合は、処理に時間がかかります。10^4 日すべての気温が同じなら、どの探索も早期には終了しません。日 0 では 9,999 日を調べ、日 1 では 9,998 日を調べるため、比較回数の合計は約 n²/2 = 5 × 10^7 になります。探索範囲も重複します。日 1 の探索は、日 0 がすでに調べた範囲とほぼ同じ範囲をたどりますが、そこから得られる新しい情報はありません。
アルゴリズム
- 各日につき1つの要素を持つ、0で初期化した回答配列を作成します。
- 各日
iについて、jをi+1から最終日まで順に調べます。 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 を書き込みます。その後、自分の暖かい日を待つことになる今日をスタックに追加します。
[71, 69, 72, 70, 70, 75, 68] を順に見ていきましょう。1日目（71）を追加します。2日目（69）は71より暖かくないので、その上に追加します。スタックには日 [0, 1] が入っています。3日目（72）が来ると、2日目（待ち時間1）、次に1日目（待ち時間2）を取り出し、その後3日目を追加します。4日目と5日目（70と70）を追加します。2つ目の70は1つ目の70を取り出しません。同じ気温は、より暖かいとはいえないためです。6日目（75）が来ると、5日目（待ち時間1）、4日目（待ち時間2）、3日目（待ち時間3）を取り出します。7日目（68）を追加します。最後まで待機中の6日目と7日目の答えは0のままです。答えは [2, 1, 3, 2, 1, 0, 0] です。
スタックの一番上だけを確認すればよい理由は、スタック内の気温が下から上へ向かって上昇しないからです。ある日を追加するのは、その上にある、より寒い日をすべて取り出した後だけなので、その下にある日はすべて、その日と同じかそれ以上に暖かいです。今日が一番上の日より暖かくなければ、その下にあるどの日よりも暖かくないため、取り出しをそこで止められます。ある日は、初めて暖かい日が現れた時点でスタックから取り出されます。したがって、記録する待ち時間は最も暖かい日までではなく、最初に来る、より暖かい日までのものです。
スタックに気温ではなくインデックスを格納するのは、答えが日数の差であり、答えのどの項目に書き込むかを知る必要があるからです。temperatures[day] を使って気温を読み戻します。各日は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
落とし穴と境界ケース
スタックループは数行で書けます。バグは比較条件とスタックに格納するものに潜んでいます。
>ではなく>=でポップする。同じ気温の日は、より暖かい日ではありません。[71, 69, 72, 70, 70, 75, 68]では、3日目は2日後の75度の日を待ちます。2日後ではなく、2日後の2番目の70度の日まで1日待つわけではありません。- インデックスではなく気温をプッシュする。答えは日数の差なので、それを計算し、どの要素に値を入れるかを知るにはインデックスが必要です。
whileが必要なところでifを使う。暖かい日が来ると、待っている日を一度に複数解決できます。最初の例では、75度の日が3日分の答えになります。- より暖かい気温、またはより暖かい日のインデックスを返す。出力するのは、何日待つかを表す
j-iです。 - スタックに残った日の答えを未設定のままにする。その答えは0です。Cでは、
callocを使って答えを確保するか、値を埋めてください。mallocで確保したメモリには不定値が入っています。 - 前方向の走査を最初により暖かい日が見つかった後も続ける。
breakがないと、最初ではなく最後に見つかった、より暖かい日を記録してしまいます。
よくある質問4
Daily Temperatures の時間計算量は何ですか？
単調スタックによる解法は、時間計算量が O(n)、追加の空間計算量が O(n) です。各日は一度だけプッシュされ、ポップされるのは最大でも一度なので、全体を通して内部ループの実行回数は最大でも n 回です。各日から前方へ走査すると、時間計算量は O(n²) となり、より暖かい日がない場合、10^4 日に対して比較回数は約 5 × 10^7 回です。
スタックには、なぜ気温ではなくインデックスを格納するのですか？
ある日の答えは距離、つまり today - day なので、その日の位置が必要です。日が取り出されたとき、インデックスは答えの配列のどの要素を埋めるかも示します。気温は temperatures[day] で取得できるので、それも保存しても何も増えません。
Daily Temperatures はスタックを使わずに解けますか？
はい。最後の日から最初の日へと進み、日 i では j = i+1 から始めます。日 j の気温がそれより高くない間は、日 j に対する答えの日、つまり j + answer[j] へジャンプします。answer[j] が 0 なら、それより気温が高い日は存在しないため、日 i にも 0 を設定します。ジャンプによって答えになり得ない日をすべて飛ばせるので、各日は高々1回しか飛ばされず、答えの配列以外にメモリを使わずに時間計算量は O(n) のままです。
Daily Temperatures は「次に大きい要素」とどのように関連していますか？
すべての位置について、同じ質問をします。右側にある次のより大きな値を見つけましょう。Next Greater Element はその値を返し、Daily Temperatures はその値までの距離を返します。そのため、スタックにはインデックスを格納します。より小さな値が出たときにポップするように反転させた同じ単調スタックで、次に小さい要素についての問題にも答えられます。
Python
def dailyTemperatures(temperatures):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
temperatures = [71, 69, 72, 70, 70, 75, 68]
期待値
[2, 1, 3, 2, 1, 0, 0]