Problem statement

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

Solution

The problem is very similar to Problem 0496: Next Greater Element I. Here we again traverse numbers from the end and keep stack with decreasing elements. The idea is to keep so-called monotonic stack: we always have elements in decreasing order while we traversing temperatures from the end. Each time we have new element first we check if we have decreasing property and if not, pop elements. Then add new element. Also if length of stack is equal to 1, it means that there is no future day with warmer temperature.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def dailyTemperatures(self, T):
        stack, out = [], []

        for i in range(len(T)-1, -1, -1):
            while stack and stack[-1][0] <= T[i]:
                stack.pop()
            stack.append((T[i], i))
            if len(stack) == 1:
                out.append(0)
            else:
                out.append(stack[-2][1] - stack[-1][1])
            
        return out[::-1]

Remark

There is also O(Wn) time complexity solution, where W is possible range of temperatures, and for each given temperature we need to check only places for O(W) bigger temperatures.