Problem statement

https://binarysearch.com/problems/Wallstreet-Bets/

Solution

Equal to Leetcode 0739 Daily Temperatures, but with big range of values, so we need to use monotonic deque here.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(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]