Online Stock Price Span

medium stack monotonic design

Problem

Stream daily stock prices through next(price) and return the span — the count of consecutive days ending today with price ≤ today's. Maintain a stack of (price, span) pairs; when today's price is ≥ the top, absorb the top's span and pop. Amortised O(1) per call.

Inputprices = [100, 80, 60, 70, 60, 75, 85]

Output[1, 1, 1, 2, 1, 4, 6]

75 absorbs 60 (×2) and 70, span 4. 85 absorbs everything down to 100, span 6.

prices (comma-separated)

class Spanner:
    def __init__(self): self.stack = []
    def next(self, price):
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

class Spanner {
  constructor() { this.stack = []; }
  next(price) {
    let span = 1;
    while (this.stack.length && this.stack[this.stack.length - 1][0] <= price) {
      span += this.stack.pop()[1];
    }
    this.stack.push([price, span]);
    return span;
  }
}

class Spanner {
    private Deque<int[]> stack = new ArrayDeque<>();
    public int next(int price) {
        int span = 1;
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1];
        }
        stack.push(new int[]{ price, span });
        return span;
    }
}

class Spanner {
    stack<pair<int,int>> st;
public:
    int next(int price) {
        int span = 1;
        while (!st.empty() && st.top().first <= price) {
            span += st.top().second; st.pop();
        }
        st.push({ price, span });
        return span;
    }
};

Time: amortised O(1) per call Space: O(n)