Daily Temperatures
Problem
For each day, return how many days you must wait until a warmer temperature, or 0 if no warmer day follows.
Example 1
Input: [73, 74, 75, 71, 69, 72, 76, 73] Output: [1, 1, 4, 2, 1, 1, 0, 0]
Test cases
Case 1
Input: [73,74,75,71,69,72,76,73] Expected: [1,1,4,2,1,1,0,0]
Case 2
Input: [30,40,50,60] Expected: [1,1,1,0]
Case 3
Input: [50] Expected: [0]
View solutionHide solution1 approach
1. Monotonic decreasing stack of indices
Time O(n)Space O(n)
Keep days still waiting for a warmer one. A warmer day pops and answers every colder day on top.
function dailyTemperatures(t) { const res = new Array(t.length).fill(0), st = []; for (let i = 0; i < t.length; i++) { while (st.length && t[i] > t[st[st.length - 1]]) { const j = st.pop(); res[j] = i - j; } st.push(i); } return res;}