Solution Explanation: Online Stock Span

This problem requires designing a data structure that efficiently calculates the stock span for each day. The stock span is defined as the maximum number of consecutive days (including the current day) where the stock price was less than or equal to the current day's price.

Approach: Monotonic Stack

The most efficient approach uses a monotonic stack. A monotonic stack is a stack that maintains a specific order (either strictly increasing or strictly decreasing). In this case, we'll use a decreasing monotonic stack.

The stack will store pairs of (price, span). The price is the stock price on a particular day, and span is the span calculated for that day.

Algorithm:

1. Initialization: Create an empty stack.

2. next(price) function:

   • Initialize span to 1. This represents the span for the current day (at least the current day itself).
   • While loop: While the stack is not empty and the top element's price is less than or equal to the current price, pop the top element. Add the popped element's span to the current span. This signifies that the current price is greater than the previous days and thus the span extends.
   • Push: Push the (price, span) pair onto the stack.
   • Return: Return the calculated span.

Time Complexity: O(N), where N is the number of calls to the next function. In the worst case, each call to next might iterate through the entire stack, but each element is pushed and popped at most once.

Space Complexity: O(N), in the worst case, the stack might store all the price-span pairs processed so far.

Code Examples (with explanations):

The code implementations in different languages demonstrate the algorithm:

Python:

class StockSpanner:
    def __init__(self):
        self.stk = [] # Initialize an empty stack to store (price, span) pairs
 
    def next(self, price: int) -> int:
        cnt = 1 # Initialize the span for current day to 1
        while self.stk and self.stk[-1][0] <= price: # Check the stack and pop elements if the condition is met
            cnt += self.stk.pop()[1] # Add the span of the popped element to current span
        self.stk.append((price, cnt)) # Push the current (price, span) onto the stack
        return cnt # Return the calculated span

Java:

import java.util.Deque;
import java.util.ArrayDeque;
 
class StockSpanner {
    private Deque<int[]> stk = new ArrayDeque<>(); //Use Deque for stack operations
 
    public int next(int price) {
        int cnt = 1;
        while (!stk.isEmpty() && stk.peek()[0] <= price) {
            cnt += stk.pop()[1];
        }
        stk.push(new int[] {price, cnt});
        return cnt;
    }
}

The Java and other language implementations follow the same logic as the Python code, using the appropriate data structures for stacks in their respective languages. The core algorithm remains consistent. Note the use of Deque in Java for efficient stack operations. Other languages use similar stack implementations (e.g., stack in C++, VecDeque in Rust).

This monotonic stack approach provides an efficient and elegant solution to the Online Stock Span problem, optimizing both time and space complexity.