Online Stock Span Visualizer & Step-by-Step Algorithm Solution

Calculate the span of stock prices in an online stream using a monotonic decreasing stack tracking [price, span] pairs.

Category: stack | Difficulty: Medium

Tags: Stack, Monotonic Stack, Design, Data Stream

Online Stock Span

Daily Stock Prices Stream (quotes)
100
0
80
1
60
2
70
3
60
4
75
5
85
6
Daily Price Spans (consecutive days <= price)
—
0
—
1
—
2
—
3
—
4
—
5
—
6
Push / Pop (Top)
(Empty Stack)
Monotonic Stack [price, span]
100%
state
day—
price—
stackTopempty
stackSize0
totalQuotes7
stream[100, 80, 60, 70, 60, 75, 85]
Initialization
1/65
Explanation

Instantiate StockSpanner to process a stream of 7 daily stock prices.

Source Code
1class StockSpanner {
2 stack: [number, number][] = []; // [price, span]
3 next(price: number): number {
4 let span = 1;
5 while (this.stack.length && this.stack[this.stack.length - 1][0] <= price) {
6 const popped = this.stack.pop()!;
7 span += popped[1];
8 }
9 this.stack.push([price, span]);
10 return span;
11 }
12}