PROBLEM DESCRIPTION
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.
SOLUTION
Here we are pushing Pair<Temperature, Index> to the stack, but it can also be solved by just pushing in the indices.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
Stack<Pair> stack = new Stack<>();
int[] nearest = new int[n];
//init
nearest[n-1] = 0;
stack.push(new Pair(temperatures[n-1], n-1));
//check nearest for other temperatures
for(int i=n-2; i>=0; i--){
//if the temperature of top of stack is higher, we can say that it's the nearest warmer one
//the current temperature can be the answer for other temperature on the left, so we push that to stack as well
if(stack.peek().temperature > temperatures[i]){
nearest[i] = stack.peek().index - i;
stack.push(new Pair(temperatures[i], i));
//if temperature on top of stack is not higher than the current, pop that
}else{
//keep popping it until stack is empty OR we have got a temperature which is more than the current temperature
while(stack.size() > 0 && stack.peek().temperature <= temperatures[i]){
stack.pop();
}
//if stack turns out to be empty => there is no warmer temperature
//so mark it as 0 and push the current temperature to stack which can be answer for other places
if(stack.size() == 0){
nearest[i] = 0;
stack.push(new Pair(temperatures[i], i));
//otherwise, we have a warmer temperature for the current one
//save it and push the current temperature back to the stack
}else{
nearest[i] = stack.peek().index - i;
stack.push(new Pair(temperatures[i], i));
}
}
}
return nearest;
}
}
class Pair{
int temperature;
int index;
public Pair(int temperature, int index){
this.temperature = temperature;
this.index = index;
}
}
BETTER CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
// Get the number of days
int n = temperatures.length;
// Stack to store pairs of temperature and index
Stack<int[]> stack = new Stack<>(); // [temperature, index]
// Result array to store the number of days to wait for a warmer temperature
int[] res = new int[n];
// Loop through each day
for(int i = 0; i < n; i++) {
// If the stack is empty, push the current temperature and index
if(stack.isEmpty()) {
stack.push(new int[]{temperatures[i], i});
continue;
}
// While stack is not empty and the current temperature is higher than the temperature at the top of the stack
while(!stack.isEmpty() && temperatures[i] > stack.peek()[0]) {
// Calculate the number of days to wait and store it in the result array
res[stack.peek()[1]] = i - stack.peek()[1];
// Remove the top element from the stack
stack.pop();
}
// Push the current temperature and index onto the stack
stack.push(new int[]{temperatures[i], i});
}
// Return the result array
return res;
}
}