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 of the stock’s price today is defined as the maximum number of consecutive days (including today) the price of the stock was less than or equal to today’s price.

Implement the StockSpanner class:

• StockSpanner() Initializes the object.
• int next(int price) Returns the span of the stock’s price given today’s price.

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 StockSpanner stockSpanner = new StockSpanner(); stockSpanner.next(100); // return 1 stockSpanner.next(80); // return 1 stockSpanner.next(60); // return 1 stockSpanner.next(70); // return 2 stockSpanner.next(60); // return 1 stockSpanner.next(75); // return 4 stockSpanner.next(85); // return 6

---

Approach in Plain English

1. For each new price, we want to know how many consecutive previous days have prices ≤ current price.
2. A stack is perfect for this because we can keep track of:
   • Previous prices that are greater than the current price, or
   • Their spans for quick calculation.
3. Store pairs in the stack: (price, span).
4. When a new price comes:
   • Initialize span = 1 (today counts as 1).
   • While the top of the stack has a price ≤ current price:
     • Pop it and add its span to current span.
   • Push (price, span) into the stack.
   • Return span.

Key idea: Using a stack allows us to efficiently calculate spans without checking all previous prices.

---

Beginner-Friendly Dry Run

Take prices = [100, 80, 60, 70, 60, 75, 85].

1. Initialize stack = [].
2. Price = 100:
   • span = 1
   • stack empty → push (100, 1)
   • return 1
3. Price = 80:
   • span = 1
   • top = 100 > 80 → cannot pop
   • push (80, 1)
   • return 1
4. Price = 60:
   • span = 1
   • top = 80 > 60 → cannot pop
   • push (60, 1)
   • return 1
5. Price = 70:
   • span = 1
   • top = 60 ≤ 70 → pop → add span 1 → span = 2
   • top now = 80 > 70 → stop
   • push (70, 2)
   • return 2
6. Price = 60:
   • span = 1
   • top = 70 > 60 → cannot pop
   • push (60, 1)
   • return 1
7. Price = 75:
   • span = 1
   • top = 60 ≤ 75 → pop → span = 2
   • top = 70 ≤ 75 → pop → span = 4
   • top = 80 > 75 → stop
   • push (75, 4)
   • return 4
8. Price = 85:
   • span = 1
   • top = 75 ≤ 85 → pop → span = 5
   • top = 80 ≤ 85 → pop → span = 6
   • top = 100 > 85 → stop
   • push (85, 6)
   • return 6

Result = [1, 1, 1, 2, 1, 4, 6]

---

Textual Approach

1. Use a stack to store (price, span).
2. For each new price:
   • Start span = 1.
   • While stack not empty and top price ≤ current price:
     • Pop top → add its span to current span.
   • Push (price, span) → return span.
3. This ensures each element is pushed/popped at most once, giving O(n) overall time.

---

Java Code

import java.util.Stack;

class StockSpanner {

    private Stack<int[]> stack; // Each element: [price, span]

    public StockSpanner() {
        stack = new Stack<>();
    }
    
    public int next(int price) {
        int span = 1;
        
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1]; // Add span of smaller/equal price
        }
        
        stack.push(new int[]{price, span});
        return span;
    }

    public static void main(String[] args) {
        StockSpanner stockSpanner = new StockSpanner();
        System.out.println(stockSpanner.next(100)); // 1
        System.out.println(stockSpanner.next(80));  // 1
        System.out.println(stockSpanner.next(60));  // 1
        System.out.println(stockSpanner.next(70));  // 2
        System.out.println(stockSpanner.next(60));  // 1
        System.out.println(stockSpanner.next(75));  // 4
        System.out.println(stockSpanner.next(85));  // 6
    }
}

---

Key Points

• Stack stores (price, span) for efficient previous price lookup.
• Time Complexity: O(n) → each price pushed/popped once.
• Space Complexity: O(n) → stack may store all prices in worst case.
• Beginner tip: Think of the span as “count of consecutive days ≤ today”, and stack helps jump over smaller prices efficiently.