The link to the problem: https://leetcode.com/problems/daily-temperatures/
Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.
Constraints:
- The length of
temperatureswill be in the range[1, 30000]. - Each temperature will be an integer in the range
[30, 100].
Example:
Input: [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]Thoughts:
For this problem, I’m going to use 4 different ways to show how we can solve this problem.
The most simple solution to solve this problem is using O(n²). If we are at day i, then we can go from day (i+1) to the end to search the first day that has a higher temperature than today (day i).
Below is the 1002ms code that using the logic —
public int[] dailyTemperatures(int[] T) {
int n = T.length;
int[] rst = new int[n];
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++) //find the first hot day
{
if(T[j]>T[i])
{
rst[i] =j-i;
break;
}
}
}
return rst;
}Let’s think if we can come up with an O(n) solution. Since the problem has mentioned about there is some range condition, we can use an array, map, to store the temperature that appears on which day. i.e., map[i] represents the day that is closest to today has temperature i. (The reason that we can consider that day is most recent is that we will overwrite the value if there are more than two days that have the same temperature, hence the later day will replace the earlier days.)
Since the range of temperature is from 30 to 100, it is wasting memory if we create a length 101 array since we will not use map[0]~map[29] at all. Hence, we will create a length 71 array and let map[0] represents what’s the most recent day we have met a temperature of 30 F.
When we are at day i, we are going to search the map array to see if so far we have met any temperature that is higher than today. We will need to traverse every temperature that is higher than today and find the minimum day number. (because the minimum day number is the most recent day compared to today) Since we want to know the temperatures of the days that are after day i, we need to traverse the whole temperature array from the last day to the first day.
Since we will at most run 71 times (i.e., the size of our map array) each day, the time complexity is O(71n), which can also write as O(n).
Below is the 15ms code that beats 66% —
public int[] dailyTemperatures(int[] T) {
int n = T.length;
int[] rst = new int[n];
int[] map = new int[71];
for(int i=n-1;i>=0;i--)
{
int cur = T[i]-30; //today's temperature
int minDay = n;
for(int temp=cur+1;temp<=70;temp++)
{
if(map[temp]==0)
continue;
minDay = Math.min(minDay, map[temp]);
}
map[cur] = i;
if(minDay!=n)
rst[i] = minDay-i;
}
return rst;
}You might found that it is not the optimal solution since we will need to search the whole map array that has a higher temperature than today(even it is a constant when we have a very large temperature array).
Hence, if we reverse the logic — instead of finding the days hotter than today (day i), let’s find the previous days that are colder than today. If the days are colder than today and haven’t been matched with other hot days, then we will let the day i be their most recent hot day.
We can use a data structure to store those days that haven’t find the most recent hot day to that day. We should use a Stack since we want to get the most recent day from day i.
Below is the 13ms code that beats 86% —
public int[] dailyTemperatures(int[] T) {
int n = T.length;
int[] rst = new int[n];
Stack<Integer> stack = new Stack<>();
for(int i=0;i<n;i++)
{
while(!stack.isEmpty() && T[i]> T[stack.peek()])
{
int indx = stack.pop();
rst[indx] = i - indx;
}
stack.push(i);
}
return rst;
}In the above two solutions, we need to use an extra space O(n) to help us decrease the time complexity from O(n²) to O(n). Next, I’m going to introduce how we can solve this problem using O(n) with O(1) space complexity.
Code Logic:
This time, we are going to do some modification to our O(n²) code which is at the very beginning of this story. Maybe using a little bit of dynamic programming concept- we are going to use the “known knowledge” to find the most recent hot day for day i.
In the original code, we are traversing the whole array from day 0 to the last day, and every time when we are at day i, we will traverse the days after i to find the first hot day. Hence, if we already help the future days to find their most recent hot day, then the most recent hot day for the day i might be in those days.
Since we are going to use the results of future days as our “known knowledge”, we need to traverse from the last day back to the first day. When we are at day i, we will set j as our next day, and our goal is to let j always points to the possible hot day.
Several conditions of how we update the value of j or if we just stop finding the possible hot day:
- If the temperature on Day j (some future day) is higher than Day i (today), it means we just found the most recent hot day for today, we will set the day difference to our rst[i] and break the loop.
Since we are traversing from backward, it means we can know what is the next hotter day for Day j —
2. If Day j is colder AND there is no hotter day for Day j (i.e., rst[j]=0), then we know that it is also impossible for Day i to find a hotter day.
3. If Day j is colder AND there is a hotter day for Day j, then that day (i.e., Day (j + rst[j]) ) might be a hot day for Day i. Hence, we will set j to that value and repeat the same process of comparing the temperature of Day i and Day j again.
Below is the 3ms code that beats 99% on Leetcode —
public int[] dailyTemperatures(int[] T) {
int n = T.length;
int[] rst = new int[n];
for(int i=n-1;i>=0;i--)
{
int j = i+1;
while(j<n)
{
if(T[j]>T[i])
{
rst[i] = j-i;
break;
}
//if T[j] is colder
if(rst[j]==0) //impossible
break;
j += rst[j]; //then jump to the day hotter than T[j]
}
}
return rst;
}
