Given some temperatures, we return an array that correlates to the number of days we’ll have to wait for a higher temperature to appear. A brute force solution would have a time complexity of O(n^2), wherein for each temperature we’d iterate through the rest of the list to find the next higher temperature.
Instead, we can use a monotonic stack to keep track of the indicies of the temperatures we’ve seen so far. It’s monotonic because we will only begin to pop values once we’ve encountered a temperature higher than the one at the top of the stack. When we pop the top of the stack, we receive an index that has a lower temperature than the current day. We update its answer by subtracting the current day’s index from the previous day.
The solution is as follows:
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stack = []
answer = [0] * len(temperatures)
for i in range(len(temperatures)):
while stack and temperatures[stack[-1]] < temperatures[i]:
j = stack.pop()
answer[j] = i - j
stack.append(i)
return answer_ Time Complexity:
O(n) - We iterate through the list once.
_ Space Complexity:
O(n) - We maintain a monotonic stack that could grow to n in the worst case.