739. Daily Temperatures

Problem

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ᵗʰ day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

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]

Constraints:

1 <= temperatures.length <= 10⁵
30 <= temperatures[i] <= 100

Test Cases

1 2	class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]:

solution_test.py

import pytest

from solution import Solution
from solution2 import Solution as Solution2


@pytest.mark.parametrize('temperatures, expected', [
    ([73,74,75,71,69,72,76,73], [1,1,4,2,1,1,0,0]),
    ([30,40,50,60], [1,1,1,0]),
    ([30,60,90], [1,1,0]),

    ([89,62,70,58,47,47,46,76,100,70], [8,1,5,4,3,2,1,1,0,0]),
])
@pytest.mark.parametrize('sol', [Solution(), Solution2()])
class Test:
    def test_solution(self, sol, temperatures, expected):
        assert sol.dailyTemperatures(temperatures.copy()) == expected

Thoughts

跟 496. Next Greater Element I 和 503. Next Greater Element II 类似，本质都是求当前元素右侧第一个比当前元素大的数，利用单调栈求解。本题是要计算找到的 next greater 温度的下标，与当前温度下标的差值。为了方便得到 next greater 的下标，直接把下标入栈。

Code

Backward Iteration

solution.py

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        answer = [0] * n
        stack = []
        for i in range(n - 1, -1, -1):
            t = temperatures[i]
            while stack and temperatures[stack[-1]] <= t:
                stack.pop()

            if stack: answer[i] = stack[-1] - i
            stack.append(i) # t is greater than temperatures[stack[-1]].

        return answer

Forward Iteration

solution2.py

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        stack = []
        for i, t in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < t:
                j = stack.pop()
                temperatures[j] = i - j
            stack.append(i)

        for i in stack:
            temperatures[i] = 0

        return temperatures