Daily Temperatures
Given an array of integers temperatures that denotes daily temperatures, return an array result where result[i] represents the number of days after the i-th day until a day with a higher temperature occurs. If no future day has a higher temperature, set result[i] to 0.
Examples
Input: temperatures = [50,60,72] Output: [1,1,0]
- For day 0 (50°F), the next warmer day is day 1 (60°F), so
result[0]= 1. - For day 1 (60°F), the next warmer day is day 2 (72°F), so
result[1]= 1. - For day 2 (72°F), there is no warmer day, so
result[2]= 0.
We can solve the Daily Temperatures problem using a monotonic stack because we are trying to find, for each day's temperature, the next day that is warmer. This fits a pattern where we need to compare each element with the elements after it, and determine when a larger value appears — a classic use case for a stack-based approach in O(n) time.
A monotonic decreasing stack allows us to efficiently keep track of candidate indices whose warmer day hasn’t been found yet. As we iterate, we pop from the stack when we find a warmer temperature and compute the difference in days.
A stack is a generic LIFO (Last-In-First-Out) data structure used to store and retrieve elements in reverse order.
A monotonic stack is a specialized stack that maintains elements in either increasing or decreasing order (monotonicity) as they are pushed.
Algorithm
Initialize: A stack to store pairs of (index, temperature) for unresolved days. A result array of zeros with the same length as temperatures.
Iterate Through Days: For each i, while the current temperature is warmer than the temperature at the top of the stack, it means we’ve found the next warmer day for the index on the stack.
Pop from the stack and calculate res[prev_index] = i - prev_index.
Push (i, temperatures[i]) onto the stack.
Remaining Stack: Any entries left in the stack did not find a warmer day — their result remains 0 (already initialized).
from typing import List
def daily_temperatures(temperatures: List[int]) -> List[int]:
stack = []
res = [0]*(len(temperatures))
for i in range(len(temperatures)):
while stack and stack[-1][1] < temperatures[i]:
idx, tmp = stack.pop()
res[idx] = i - idx
stack.append([i, temperatures[i]])
return resTime Complexity: O(n). Each element is pushed and popped at most once from the stack.
Space Complexity: O(n). For the stack and the result array.