Daily Temperatures

Problem

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

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 i:sup:`th` 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:sup:`5`

• 30 <= temperatures[i] <= 100

Pattern

Array, Stack, Monotonic Stack

Approaches

Monotonic Stack

Code

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    stack = []

    output = [0] * len(temperatures)

    for i, temp in enumerate(temperatures):

        while len(stack) > 0 and temperatures[stack[-1]] < temp:
            j = stack.pop()
            output[j] = i - j

        stack.append(i)

    return output

Test

>>> from daily_temperatures__monotonic_stack import dailyTemperatures
>>> dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73])
[1, 1, 4, 2, 1, 1, 0, 0]
>>> dailyTemperatures([30, 40, 50, 60])
[1, 1, 1, 0]
>>> dailyTemperatures([30, 60, 90])
[1, 1, 0]

daily_temperatures__monotonic_stack.dailyTemperatures(temperatures: list[int]) → list[int]