739. Daily Temperatures Medium

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^{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]

Approach

Input: An integer array temperatures representing the daily temperatures

Output: Return an array representing the number of days until a warmer temperature for each day

This problem belongs to the Monotonic Stack category.

• We can maintain a monotonically decreasing stack, where temperatures are decreasing from the bottom of the stack to the top.
• The stack stores the indices index.

We can iterate through the array from back to front, comparing the current temperature with the top element of the stack each time. As long as it is greater than or equal to the element in the stack, we remove the element from the stack until we encounter an index with a temperature strictly greater than the current temperature.

For example: 80 -> [90, 78, 72, 70] =====> [90, 80]

When an index with a greater temperature is found, we obtain the answer corresponding to the current temperature: ans[i] = st[-1] - i.

Finally, after traversing the entire array, we have the answer for each day.

Implementation

python

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        stack = []  # Monotonically decreasing stack, stores indices (stack top is the nearest warmer day)
        res = [0] * n  # Result array, default value is 0

        # Traverse from back to front (because we need to find warmer days in the future)
        for i in range(n - 1, -1, -1):
            current_temp = temperatures[i]

            # Keep only the indices of days with a temperature higher than the current
            while stack and temperatures[stack[-1]] <= current_temp:
                stack.pop()

            # If the stack is not empty, it means we found a day with a higher temperature
            if stack:
                res[i] = stack[-1] - i  # Calculate the number of days in between

            # Push the current day into the stack as a "future" for the previous elements
            stack.append(i)

        return res

javascript

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
    const st = [];
    const ans = new Array(temperatures.length).fill(0);

    for (let i = temperatures.length - 1; i >= 0; i--) {
        const t = temperatures[i];
        while (st.length && t >= temperatures[st.at(-1)]) {
            st.pop();
        }

        if (st.length) {
            ans[i] = st.at(-1) - i;
        }

        st.push(i);
    }

    return ans;
};

Complexity Analysis

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

Links

739. Daily Temperatures (English)

739. 每日温度 (Chinese)