Problem description

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].

Example 1:

Input: [“StockSpanner”,”next”,”next”,”next”,”next”,”next”,”next”,”next”], [[],[100],[80],[60],[70],[60],[75],[85]] Output: [null,1,1,1,2,1,4,6] Explanation: First, S = StockSpanner() is initialized. Then: S.next(100) is called and returns 1, S.next(80) is called and returns 1, S.next(60) is called and returns 1, S.next(70) is called and returns 2, S.next(60) is called and returns 1, S.next(75) is called and returns 4, S.next(85) is called and returns 6.

Note that (for example) S.next(75) returned 4, because the last 4 prices (including today’s price of 75) were less than or equal to today’s price.

Solution

1. The stream operation can usually be solved by montonous stack. For this problem, we can keep a monotonous decreasing stack of stock price and its span tuple. If stack not empty, we compare the price of stack top with current price, if stack top price is equal to or smaller than current price, we need to add stack top span to the current span. We need to perform this operation until the stack top price is larger than current price or the stack is empty. Then we push the current price and span to the stack.
2. Loop-invariant are
   1. The top of the stack is always the current price and its span.
   2. The stack is decreasing with price
3. Below is the code implementation

class StockSpanner:

    def __init__(self):
        self.stack = [] # a monotonous decreasing stack with price and the corresponding span

    def next(self, price: int) -> int:
        current_span = 1
        while self.stack and self.stack[-1][0] <= price:
            p, span = self.stack.pop()
            current_span += span
        self.stack.append((price, current_span))
        return current_span

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