Daily Temperatures

LeetCode 739 · View on LeetCode

Use a monotonic decreasing stack of indices. When a warmer day is found, pop all cooler days from the stack and compute the distance.

def daily_temperatures(temperatures: list[int]) -> list[int]:
    result = [0] * len(temperatures)
    stack = []  # indices of days waiting for a warmer day
    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev = stack.pop()
            result[prev] = i - prev
        stack.append(i)
    return result

if __name__ == '__main__':
    print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))  # [1,1,4,2,1,1,0,0]
    print(daily_temperatures([30, 40, 50, 60]))                    # [1,1,1,0]
    print(daily_temperatures([30, 20, 10]))                        # [0,0,0]