Online Stock Span

Medium

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}
}