739.Daily_Temperatures(Medium).md

739. Daily Temperatures (Medium)

Date and Time: Jul 15, 2024, 21:10 (EST)

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

Question:

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

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]

Constraints:

• 1 <= temperatures.length <= 10^5

• 30 <= temperatures[i] <= 100

KeyPoints:

We use stack (monotonic decreasing stack) to keep track of the previous lower temperatures and its index. If current t is larger than the last element in stack, we can start popping all the elements are lower than t, and add the indices i - stack[-1][0] to res.

My Solution:

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        # Stack = [[index, temperature]]  (monotonic increasing)
        # Update the previous index in res by current larger temperature's index

        # TC: O(n), SC: O(n)
        stack = []
        res = [0] * len(temperatures)
        for i, temp in enumerate(temperatures):
            while stack and temp > stack[-1][1]:
                # Update prev temp's index in res with i - prev's index
                res[stack[-1][0]] = i - stack[-1][0]
                stack.pop()
            stack.append([i, temp])
        
        return res

Time Complexity: $O(n)$
Space Complexity: $O(n)$