Online Stock Span

Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock's price for the current day.

The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price.

For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].

Approach: Monotonic Stack

To tackle this problem, we'll again make the use of the monotonic Stack.

A monotonic stack keeps stack elements always ordered (either increasing or decreasing ). As it relates to our algorithm, price span will track the span of smaller elements as it is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price.

Therefore, we choose monotonic stack with decreasing order as data structure to support our implementation.

Time Complexity: O(N) ---> we'll iterate over the array once

Space Complexity: O(N) ---> Ex: Let's consider that the stock's quote ever decreases, in the worst case, the stack will contain all the daily price quotes. [100, 80, 60, 50, 40, 35]

Class StockSpanner:

     def __init__(self):
        self.stack = collections.deque()

     def next(self, price: int)-> int:
        span = 1
        while self.stack and price >= self.stack[-1].price_quote:
            span += self.stack.pop().price_span

        self.stack.append(Stock(price, span))

        return span
 
Class Stock:
    def __init__(self, price_quote, price_span):
        self.price_quote = price_quote
        self.price_span = price_span