Online Stock Span

class StockSpanner {
public:
    stack<pair<int, int>> pricesStack;
    int next(int price) {
        int span = 1;
        while (!pricesStack.empty() && pricesStack.top().first <= price) {
            span += pricesStack.top().second;
            pricesStack.pop();
        }
            
        pricesStack.push({price, span});
        return span;
    }
};
    
/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner* obj = new StockSpanner();
 * int param_1 = obj->next(price);
 */

This solution implements a class called StockSpanner to solve the stock span problem, where the task is to calculate the maximum number of consecutive days the stock price has been less than or equal to the current day's price. The solution effectively utilizes the stack data structure to optimize the span calculation, making it efficient for sequences of stock prices.

• Initialize a stack pricesStack in your class to keep track of price and span pairs.
• Define the next function which takes the current day's stock price as an input:
  • Start with a span of 1 for the current day.
  • Use a while loop to check and process the conditions where the top of the stack has a price less than or equal to the current price.
  • For each element in the stack satisfying the condition, add its span to the current day's span and remove it from the stack.
  • Push the current day's price and calculated span as a pair onto the stack.
  • Return the span for the current price.

This structured approach ensures efficient handling of price data and quick retrieval of the span using the properties of the stack. Each price is pushed and popped from the stack at most once, leading to an average time complexity per operation that is efficient for large data inputs.

class StockSpanner {
    Stack<int[]> history = new Stack<>();
        
    public int next(int currentPrice) {
        int span = 1;
        while (!history.isEmpty() && history.peek()[0] <= currentPrice) {
            span += history.pop()[1];
        }
            
        history.push(new int[] {currentPrice, span});
        return span;
    }
}
    
/*
 * Usage of StockSpanner class:
 * StockSpanner obj = new StockSpanner();
 * int result = obj.next(currentPrice);
 */

The problem "Online Stock Span" seeks to determine the number of consecutive days leading up to the current day where the stock price was less than or equal to the current price. Implement this functionality using a stack data structure in Java.

• Implement a class StockSpanner with:

  • A private stack history to store stock prices and their spans.

• The class contains a method next(int currentPrice):

  • Initialize the span of the stock price for the current day as 1.
  • While the stack is not empty and the price at the top of the stack is less than or equal to currentPrice, update the span by adding the span of the price at the top of the stack and remove the top value.
  • Push the current price and its computed span onto the stack.
  • Return the calculated span for the current price.

This implementation ensures that each stock price response is efficiently handled in amortized O(1) time, utilizing the stack's last-in-first-out property to keep track of the prices and spans efficiently.

class PriceSpanner:
    def __init__(self):
        self.prices = []
    
    def next_price(self, current_price: int) -> int:
        span = 1
        while self.prices and self.prices[-1][0] <= current_price:
            span += self.prices.pop()[1]
            
        self.prices.append([current_price, span])
        return span
    
# Your PriceSpanner object will be instantiated and called as such:
# obj = PriceSpanner()
# param_1 = obj.next_price(current_price)

The given Python code defines a class named PriceSpanner designed to manage and calculate the span of stock prices online. The span is the number of consecutive days leading up to and including the current day where the stock price was less than or equal to the current price.

Here's how the PriceSpanner class operates:

• Upon initialization (__init__ method), it sets up a list called prices that will store each price and its span as elements in the form of [price, span] pairs.

• The next_price method adds a new stock price to the PriceSpanner:

  1. It starts with a span of 1 for the current price.
  2. It then checks the last recorded price in the prices stack. If the current price is greater than or equal to this last recorded price, it continuously removes the last element from prices and adds its span to the current span.
  3. After updating the span, the current [price, span] pair is appended to the prices stack.
  4. Finally, the updated span for the current price is returned.

This method effectively calculates the stock span using a stack structure to store prices and their respective spans, allowing it to handle each price in constant time on average through amortized analysis. This design ensures efficient management and updating of stock information in scenarios where stock prices need to be evaluated in real-time.