題目出處

739. Daily Temperatures

難度

Medium

個人範例程式碼

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        if not temperatures:
            return []

        stack = []
        ans = [0 for _ in range(len(temperatures))]
        for today, temperature in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < temperature: # today's temperature is higher
                idx = stack.pop(-1)
                ans[idx] = today - idx
            stack.append(today)

        return ans

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

stack 的經典題型，透過 stack 紀錄沿路上的過去史，
並不斷地以「今日」去比對「過去尚未產生結果的結果」

• pop 至過去結果溫度「比今日小的所有結果」，相距日期則為「today – 該日」

input handling

如果沒有 input，return []

Boundary conditions

for 搜尋所有的天數，
如果過程中有發現更高的溫度，就去更新結果。

Reference

• 每日温度 · Daily Temperatures