Online Stock Span - Githubissues

Overview

The brute force approach involves keeping an array of all stock prices and iterating backwards on each call to next to find a price greater than the current price. This is inefficient because we repeatedly iterate over the same elements.

Example

Consider stock prices: [50, 45, 40, 35, 30]

Call next(46): We iterate back over [45, 40, 35, 30] to find 50.
Call next(47): We again iterate back over [45, 40, 35, 30] even though we did this for 46.

Monotonic Stack Approach

Intuition

For each price, find the most recent day with a higher price. When calling next(47), we first check 46. Since 46 is not greater than 47, and 30, 35, 40, 45 are also not greater than 46, they are not greater than 47 either. Thus, iterating over these elements is redundant.

Solution

A monotonic stack is always sorted. For a decreasing stack, if we push x, elements less than x are popped to maintain order. This way, we avoid redundant checks.

Example Walkthrough

Consider calls to next in the order: [100, 80, 60, 70, 60, 75, 85]. The output is [1, 1, 1, 2, 1, 4, 6].

For 100: First day, answer is 1.
For 80: Previous day is 100, which is greater, so answer is 1.
For 60: Previous day is 80, which is greater, so answer is 1.
For 70: Previous day is 60, which is not greater. The answer for 60 was 1, so we check further back to find 80, making the answer 2.

Using a monotonic decreasing stack:

Declare a stack to store prices and their respective spans.
On calling next(price), while the stack's top value is less than or equal to price, pop it and add its span to the current span.
Push the current price and its calculated span onto the stack.

This approach efficiently calculates the span without redundant iterations.

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

    def next(self, price: int) -> int:
        ans = 1
        while self.stack and self.stack[-1][0] <= price:
            ans += self.stack.pop()[1]

        self.stack.append([price, ans])
        return ans

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

fbaquant / LeetCode