Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
TC: O(n)SC: O(n)
Approach - Monotonic decreasing/equal stack
- keep adding temperatures to the stack and if the current is greater than the last pushed then we just the difference is the day it took and we store that store it in result
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] res = new int[temperatures.length];
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < temperatures.length; i++) {
while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int prev = stack.pop();
res[prev] = i-prev;
}
stack.push(i);
}
return res;
}
}