Problem
Given an array of integers temperatures, wheretemperatures[i] represents the temperature on the ith day, 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 with a warmer temperature,
answer[i] should be 0.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
temperatures = [73,74,75,71,69,72,76,73] Output
[1,1,4,2,1,1,0,0] Solution
This solution uses a Monotonic Stack to store the indices of days whose next warmer temperature has not yet been found. The temperatures corresponding to these indices are maintained in decreasing order.As each temperature is processed, it is compared with the temperature at the index on top of the stack. If the current temperature is warmer, the previous day has found its next warmer day. The difference between their indices gives the number of days to wait.
After resolving all previous days with a lower temperature, the current index is pushed onto the stack. Any indices remaining in the stack at the end do not have a future warmer temperature, so their values remain
0.
public int[] dailyTemperatures(int[] temperatures) {
int[] result = 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 previousIndex = stack.pop();
result[previousIndex] = i - previousIndex;
}
stack.push(i);
}
return result;
}
Complexity
Each index is pushed onto the stack once and popped at most once, resulting in a time complexity ofO(n). In the worst case, all indices may remain in the stack, resulting in an extra space complexity of
O(n).