Monotonic Stack
LC #901Medium
Online Stock Span
Monotonic Stack
AmazonGoogleBloombergProblem
Design a class that collects stock prices and returns the span (consecutive days with price ≤ today).
stackdesign
Constraints
- ›1 ≤ price ≤ 10⁵
- ›At most 10⁴ calls to next
Example
Input
next calls: [100],[80],[60],[70],[60],[75],[85]Output
[1, 1, 1, 2, 1, 4, 6]Why
75 has span 4: [60,70,60,75] all ≤ 75. 85 has span 6: all previous ≤ 85