Medium Monotonic Stack Stacks & Queues
In plain English: For each day, find how many days you have to wait until a warmer day comes.
Use a monotonic decreasing stack of indices. When a new temperature is higher than the stack top, pop and record the distance. Each element is pushed and popped at most once — O(n) total.
Prompt
Given an array of daily temperatures, return an array where each element says how many days until a warmer temperature. If none, put 0.
Try to write it from scratch before scrolling down.
Solution
def daily_temperatures(temps):
n = len(temps)
result = [0] * n
stack = [] # monotonic decreasing stack of indices
for i in range(n):
while stack and temps[i] > temps[stack[-1]]:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
# Test: daily_temperatures([73,74,75,71,69,72,76,73])
# == [1,1,4,2,1,1,0,0]