loading

Daily Temperatures — Step-by-Step Visualization

mediumLeetCode #739ArrayStackMonotonic Stack

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 `i-th` day to get a warmer temperature. If there is no future day for which this is possible, keep `answer[i] == 0` instead.

Algorithm Pattern

Monotonic Decreasing Stack

Key Idea

A monotonic stack is perfect for finding the 'next greater element'. We store indices of temperatures we haven't found a 'warmer day' for yet. The stack will always be in descending order of temperatures. When we see a temperature warmer than the one at the top of our stack, we know we've found the 'warmer day' for that index. We pop it, calculate the difference in indices, and store it in our result.

Step-by-Step Approach

  1. Initialize `res = [0] * len(temps)` and `stack = []`.
  2. Iterate through each temperature `T` at index `i`.
  3. While `stack` is not empty AND `T > temps[stack.top()]`:
  4. Pop index `prevIdx` from stack.
  5. Set `res[prevIdx] = i - prevIdx`.
  6. Push `i` onto stack.
  7. Return `res`.

Common Gotchas

  • Indices in the stack represent days waiting for a warmer temperature.
  • The stack stores the indices, but we compare the actual temperature values.

Related Problems

← All problems