Medium

Daily Temperatures

087

For each day, return how many days until a warmer temperature, or 0 if none exists.

EXAMPLES

Example 1

Input
{
  "temperatures": [
    73,
    74,
    75,
    71,
    69,
    72,
    76,
    73
  ]
}

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

FUNCTION SHAPE

temperatures: intArray→intArray

SOLUTION NOTE

The answer is the difference between the index of the next greater element and the current element.

Reveal reference solution +

pythonREFERENCE

def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
    stack = []
    n = len(temperatures)
    res = [0] * n
    for i in range(n):
        while stack and temperatures[stack[-1]] < temperatures[i]:
            idx = stack.pop()
            res[idx] = i - idx
        stack.append(i)
    return res

TimeO(n)

SpaceO(n)

Open on LeetCode ↗