Problem statement

https://leetcode.com/problems/online-stock-span/

Solution

The idea is to keep monotonic stack with tuples: (price, freq), where we have prices in decreasing order and freq is answer for this price. Each moment we have new price, we first check if it is smaller than self.stack[-1][0] and if it is, we add it to stack with frequency 1. If it is not, then we extract from our stack as much elements as needed, such that we have decreasing property and sum their frequencies. Finally we put new price with new frequency to stack.

Complexity

Time and space complexity is O(n) after n operations made.

Code

class StockSpanner:
    def __init__(self):
        self.stack = [(10**6, 1)]
        
    def next(self, price):
        if price < self.stack[-1][0]:
            self.stack.append([price, 1])
        else:
            count = 1
            while price >= self.stack[-1][0]:
                count += self.stack[-1][1]
                self.stack.pop()
            self.stack.append([price, count])
        return self.stack[-1][1]