Online stock span

XXX. Stock Spanner

Stack

Greedy

Problem Statement:

Design a class StockSpanner that collects daily stock prices and returns the span of the stock's price for the current day. The span is the number of consecutive days (including today) the price of the stock has been less than or equal to its price today.

Example:

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: - On the first day, the price is 100, so the span is 1. - On the second day, the price is 80, so the span is 1 (80 ≤ 100). - On the seventh day, the price is 85, and the span is 6 (85 ≥ 100, 85 ≥ 80, 85 ≥ 70, etc.).

Approach:

1. Use a stack to store pairs of [price, span], where span represents the number of consecutive days the price has been less than or equal to the current price.
2. When a new price is added, keep popping the stack while the current price is greater than or equal to the price at the top of the stack, adding the popped spans to the current span.
3. Push the current [price, span] pair onto the stack.

Algorithm Intuition:

The problem requires efficient tracking of the span of stock prices. Using a stack allows us to process each price in constant time on average. By storing spans and popping smaller prices, we calculate the span for each day efficiently without recomputing from scratch.

Complexity:

Time Complexity: O(n), where n is the number of calls to next(), as each price is pushed and popped from the stack at most once.
Space Complexity: O(n), for the stack storing n elements.

Java Implementation:

// Java implementation using a stack
class StockSpanner {

    Stack s;

    public StockSpanner() {
        s = new Stack<>(); // Stack to store [price, span]
    }

    public int next(int price) {
        int span = 1;

        // While the current price >= top of the stack, merge spans
        while (!s.isEmpty() && price >= s.peek()[0]) { 
            span += s.pop()[1]; // Add the popped span to the current span
        }

        s.push(new int[]{price, span}); // Push the current price and span
        return span;
    }
}

Python Implementation:

class StockSpanner:

    def __init__(self):
        self.stack = []  # Stack to store [price, span]

    def next(self, price: int) -> int:
        span = 1

        # While the current price >= top of the stack, merge spans
        while self.stack and price >= self.stack[-1][0]:
            span += self.stack.pop()[1]

        self.stack.append((price, span))  # Push the current price and span
        return span