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

給一個每天溫度的陣列，回傳一個陣列，值代表：今天開始「要過幾天」溫度才會比今天高

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]

December 29, 2023

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = [] # monotonic decreasing stack, store index
        res = [0] * len(temperatures)

        for i, temp in enumerate(temperatures):
            while stack and (temperatures[stack[-1]] < temp):
                res[stack[-1]] = i - stack[-1]
                stack.pop()
            stack.append(i)

        return res

time O(n)

space O(n)