Problem URL: Online stock span

We will use a stack to keep track of the previous prices. We will then iterate over the prices and pop the stack until the top of the stack is greater than the current price. We will then push the current price and the current index onto the stack. We will then return the difference between the current index and the index of the top of the stack.

class StockSpanner:
    def __init__(self):
        self.stack = [(inf, 0)]

    def next(self, price: int) -> int:
        curDay = self.stack[-1][1]+1

        while price >= self.stack[-1][0]:
            self.stack.pop()

        span = curDay - self.stack[-1][1]

        self.stack.append((price, curDay))

        return span

# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)

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