Monotonic Stack
LC #739Medium
Daily Temperatures
Monotonic Stack
AmazonGoogleMetaBloombergProblem
Given daily temperatures, return an array where answer[i] is the number of days until a warmer day.
arraystack
Constraints
- ›1 ≤ n ≤ 10⁵
- ›30 ≤ temperatures[i] ≤ 100
Example
Input
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]Output
[1, 1, 4, 2, 1, 1, 0, 0]Why
Day 0 (73°): wait 1 day for 74°. Day 2 (75°): wait 4 days for 76°