mediumStackPattern: Monotonic Stack
Daily Temperature Variations Solution
Problem Statement
Given a list of daily temperatures, return a list of the number of days until a warmer temperature occurs. If no warmer temperature occurs, return 0 for that day.
Examples
Example 1:
Input:[73, 74, 75, 71, 69, 72, 76, 73]
Output:[1, 1, 4, 2, 1, 1, 0, 0]
Explanation: For the first day with temperature 73, the next warmer day is the second day with temperature 74, so the answer is 1. For the seventh day with temperature 76, there are no warmer days, so the answer is 0.
Example 2:
Input:[10, 20, 30, 40, 50]
Output:[1, 1, 1, 1, 0]
Explanation: Each day has a warmer temperature the next day, except for the last day.
Constraints
- Array size ≤ 10^5
- All temperatures are between -10^8 and 10^8
- No duplicate temperatures in the array
- All elements in the array are integers
Time: O(n) Space: O(n)
We can use a monotonic stack to optimize the solution. The stack will store the indices of the temperatures. Whenever a warmer temperature is found, we pop the stack and update the result array. This approach reduces the time complexity to O(n).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.