NeetCode 150 [Stack]:medium 4/5

NeetCodeのSolutionを書いていく

Daily Temperatures

問題概要

気温の配列temperaturesが与えられます。
添字番目の日の気温をあらわします。
i番目の気温が次により暖かくなる日までの必須雨を返しなさい。
そのような日がない場合は0を返しなさい。

制約

• 入力の配列長さは1以上1000以下
• 気温は1以上100以下

計算時間:O(n)
メモリ：O(n)
nは入力配列サイズ

例

Input: temperatures = [30,38,30,36,35,40,28]
Output: [1,4,1,2,1,0,0]

Input: temperatures = [22,21,20]
Output: [0,0,0]

メモ

力技でやるなら、それぞれ次に暖かくなる日を探すだけで良い。
ただ、それだとO(n^2)になりそう。
スタックというお題でO(n)で実装する。
補助スタック？

全然わからなくて悔しい。
答え見た。以下の要領で実装する。

• 各日の気温を日付昇順で(入力のまま)Stackに積む
• Stackに積む時に、スタックの最後のデータと比較して積む気温より低ければpopし日付差分を計算し、戻り値に追加する

比較が必ず過去データとの比較なのでStack pushしながら比較すれば良い。
日付をまたいで比較する必要があるのでpopして比較を続ける
Stackのデータは順次評価されるので上の方のデータが比較でFalseとなればそれ以上比較する必要がない

from typing import List


class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        Stack: List = []
        result = [0 for _ in range(len(temperatures))]

        for i, t in enumerate(temperatures):
            while Stack and Stack[-1][1] < t:  # 最後の気温が今回の気温より低い
                idx, _ = Stack.pop()
                result[idx] = i - idx
            Stack.append([i, t])

        return result