Intermediate Level
Implement the dailyTemperaturesWait method that returns how many days must be waited for a warmer temperature.
The input contains an array temp and its length size. Each value represents the temperature for one day.
For each day, your task is to return how many days must be waited until a warmer temperature occurs. If no warmer future day exists, return 0 for that day.
For example, for [73,74,75,71,69,72,76,73], the answer is [1,1,4,2,1,1,0,0].
Example 1
Input
temp (int[]) =
[73,74,75,71,69,72,76,73]size (int) =
8Returns (int[])
[1,1,4,2,1,1,0,0]Example 2
Input
temp (int[]) =
[30,40,50,60]size (int) =
4Returns (int[])
[1,1,1,0]Example 3
Input
temp (int[]) =
[30,60,90]size (int) =
3Returns (int[])
[1,1,0]Use a monotonic stack of indexes for days that are still waiting for a warmer temperature.
Scan each temperature from left to right. If the current temperature is warmer than the temperature at the index on top of the stack, the waiting time for that earlier day is now known.
Keep popping and filling answers while the current day is warmer. Then push the current day index onto the stack.
Pseudocode:
function dailyTemperaturesWait(temp, size):
result = array of size filled with 0
stack = empty stack of indexes
for i from 0 to size - 1:
while stack is not empty and temp[i] > temp[top of stack]:
index = pop from stack
result[index] = i - index
push i into stack
return resultReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run