Re: [閒聊] 每日LeetCode

[JerryChungYC (JerryChung)]

https://leetcode.com/problems/daily-temperatures

739. Daily Temperatures

給一串每日溫度，回傳每日需等待幾天才會有更溫暖的溫度
如果後面沒有更溫暖的日子就回傳0

Example 1:
  Input: temperatures = [73,74,75,71,69,72,76,73]
  Output: [1,1,4,2,1,1,0,0]

Example 2:
  Input: temperatures = [30,40,50,60]
  Output: [1,1,1,0]

Example 3:
  Input: temperatures = [30,60,90]
  Output: [1,1,0]

Python3 code:
---------------------------------------------------------
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        dit = defaultdict(list)
        res = [0] * len(temperatures)
        for index, temp in enumerate(temperatures):
            dit[temp].append(index)
            for k, v in dit.items():
                if temp > k:
                    while v:
                        p = v.pop()
                        res[p] = index - p
        return res
---------------------------------------------------------

defaultdict(list) 會當沒有該 key 值時新增一個 dit[key] = []
就不用用 if 判斷 key 是否在 dit 裡面
dit 的 key 是溫度 value 是第 i 天 用來減少溫度的判斷次數

https://i.imgur.com/OTcvDWw.png

時間從贏5%變贏7.84% 哈
空間最好則是97.14%

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.227.251.103 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1706679542.A.E58.html
推 JIWP: 大師
推 SecondRun: 大師