Daily Temperatures

StackArrayMonotonic Stack

20 min

Problem Statement

Given an array of integers temperatures representing 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

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]

Input Temperatures:

Result (Days to wait):

Output: [1,1,4,2,1,1,0,0]

Solution

This problem can be efficiently solved using a monotonic stack. We use a stack to store indices of the temperatures, maintaining a decreasing order of temperatures.

Algorithm Steps

Initialize an answer array of the same size as the input, filled with zeros.
Initialize an empty stack to store indices.
Iterate through the temperatures array with their indices.
While the stack is not empty and the current temperature is greater than the temperature at the index stored at the top of the stack:
- Pop the index from the stack. This is the index of the day we've now found a warmer day for.
- Calculate the number of days waited (current index - popped index) and update the answer array.
Push the current index onto the stack.

Temperatures

Result (Days to wait)

Stack (Indices)

Start.

Daily Temperatures Solution


class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        res = [0] * len(temperatures)
        stack = []  # pair: [temp, index]

        for i, t in enumerate(temperatures):
            while stack and t > stack[-1][0]:
                stackT, stackInd = stack.pop()
                res[stackInd] = i - stackInd
            stack.append([t, i])
        return res