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