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.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73] Output: [1,1,4,2,1,1,0,0]
Example 2:
Input: temperatures = [30,40,50,60] Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90] Output: [1,1,0]
Constraints:
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100
The description was taken from https://leetcode.com/problems/minimum-size-subarray-sum/.
#O(N) Time, O(1) Spaceclass Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: output, stack = [0]*len(temperatures), [] for i, temp in enumerate(temperatures): if stack and temp < stack[-1][1]: stack.append([i, temp]) continue while stack and temp > stack[-1][1]: last_index, last_temp = stack.pop() output[last_index] = i - last_index stack.append([i, temp]) return outputAt each index, we are looking for the next index with a greater element.
Without doing a nested loop where we would compare each number with each other index after it which would require quadratic time, we can instead use a stack.
This method we will be using is known as a Monotonic Stack. It can be used to find the first lesser or greater value from each index.
The way it works is we will continuously compare each value with what value is on the stack. In this case, since we are looking for the first greater value, we will see if our current value is greater than what is on the stack. If it is not, we can't answer the question of where the next greater element is yet, so we will add our value and index to the stack and move on. If it is, we will be able to answer that question for each value we have on the stack with a lesser temperature. We will answer that question by popping each value off of the stack and looking at the index difference between those values and our current index.
Once we have finished traversing the array, we will have answered where the next greater temperature was for each value, except the values still left on a stack that we weren't able to find a greater temperature for. In those cases, we are asked to keep their value as zero.
Let's start by initializing our output array and our stack.
The description says to keep the indices of the days we weren't able to find a greater temperature for's value at zero if we couldn't find a greater temperature. That is why we are initializing our array with zeroes.
output, stack = [0]*len(temperatures), []
Next, we make an enumeration through the temperatures array. An enumeration just means we are iterating through the values of an array with a counter that also keeps track of indices.
for i, temp in enumerate(temperatures):
At the beginning of each iteration, we will start by seeing if our current temperature is less than the temperature at the top of the stack if there is one.
If it isn't, or there isn't anything on the stack, we will push our index and temperature onto the stack and continue to the next iteration.
if stack and temp < stack[-1][1]: stack.append([i, temp]) continue
This is basically our way of pushing a question onto the stack for our future selves to answer: "where is the first index with a greater temperature than the current one?".
If the current temperature is greater than the one at the top of the stack, then we can begin popping and answering questions for each day on the stack with a temperature less than the current.
While we still have a stack, and while the current temperature is greater than the temperature on top of the stack, we will pop a lesser temperature off saying "hey, your first greater temperature is right here, and you had to wait x days (the current day minus the day we were at when we asked this question)", then we will write that answer at the index of this previous, lesser temperature.
while stack and temp > stack[-1][1]: last_index, last_temp = stack.pop() output[last_index] = i - last_index
After we finish answering the questions for each lesser temperature on the stack, we will append the current day and temperature on, then await the day we have a bigger temperature and we can be popped off to know what the first greater temperature from here is.
stack.append([i, temp])
Once we have finished traversing the array, we will return the output array where each index holds how many days each day had to wait to get a greater temperature.
return output