Daily Temperatures
Introduction
Given an array of integers temperatures
answer
answer[i]
ith
answer[i] == 0
Example 1
Output: [1,1,4,2,1,1,0,0]
Example 2
Output: [1,1,1,0]
Example 3
Output: [1,1,0]
Constraints:
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
Solution 1 - Using stack, construct a monotonically decreasing stack
In this approach, we are going to build a monotonically decreasing stack, meaning that elements in the stack should be in a decreasing order, when we see a number higher than the top of the stack, then we delete elements from stack to ensure that the stack is still monotonically decreasing order.
Implementation steps:
-
First, we will create two variables
an integer array, that we are going to return as answer, andresult
astack
that we will use to store temparatures in monotonically decreasing order.Stack
-
Next, loop through input array
and add the current element's index into thetemperatures
, but before adding the current index into thestack
we need to make sure that it it monotonically decreasing order. So, what we will do is check the top of the stack element and see if its corresponding value is smaller than current element, then we will remove that index fromstack
. While doing this check, we will also fillb-v
array, we will update stack's top element index inresult
withresult
, this means that the current element next greater element, and it is ati - stack's top
distance.i- index stored in stack
import java.util.Arrays;
import java.util.Stack;
public class DailyTemperatures {
static 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[stack.peek()] < temperatures[i]) {
result[stack.peek()] = i-stack.peek();
stack.pop();
}
stack.push(i);
}
return result;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(dailyTemperatures(new int[]{73,74,75,71,69,72,76,73})));
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n) time where n
temperatures
Space complexity: O(n).
Above implementations source code can be found at