Online Stock Span
Problem
Prices arrive one per day. For each new price, return its span: the number of consecutive days, ending today and going backwards, on which the price was ≤ today's price.
Example 1
Input: 100, 80, 60, 70, 60, 75, 85 Output: 1, 1, 1, 2, 1, 4, 6
Test cases
Case 1
Input: new StockSpanner() .next(100) .next(80) .next(60) .next(70) .next(60) .next(75) .next(85) Expected: [1,1,1,2,1,4,6]
Case 2
Input: new StockSpanner() .next(10) .next(10) .next(10) Expected: [1,2,3]
Case 3
Input: new StockSpanner() .next(3) .next(2) .next(1) Expected: [1,1,1]
View solutionHide solution1 approach
1. Monotonic stack of [price, span]
Time O(1) amortised per callSpace O(n)
Absorb every earlier price ≤ today’s, adding their spans. Each price is pushed and popped once.
class StockSpanner { constructor() { this.st = []; } next(price) { let span = 1; while (this.st.length && this.st[this.st.length - 1][0] <= price) span += this.st.pop()[1]; this.st.push([price, span]); return span; }}