#739 - Daily Temperatures

MediumMonotonic Stack

Given an array temperatures, return an array answer where answer[i] is the number of days you have to wait after day i to get a warmer temperature. If there is no future warmer day, answer[i] = 0.

Input	Output
temperatures = [73,74,75,71,69,72,76,73]	[1,1,4,2,1,1,0,0]
temperatures = [30,40,50,60]	[1,1,1,0]
temperatures = [30,60,90]	[1,1,0]

Solution Space

Try it

/**
 * For each day, finds how many days until a warmer temperature.
 * Uses a monotonic decreasing stack of indices.
 *
 * @param temperatures Daily temperature readings
 * @returns Wait-days array (0 if no warmer day exists)
 */
export function dailyTemperatures(temperatures: number[]): number[] {
  const n = temperatures.length;
  const answer = new Array<number>(n).fill(0);
  const stack: number[] = []; // indices of days waiting for a warmer day

  for (let i = 0; i < n; i++) {
    // Pop all days that are colder than today
    while (
      stack.length > 0 &&
      temperatures[i] > temperatures[stack[stack.length - 1]]
    ) {
      const prev = stack.pop()!;
      answer[prev] = i - prev;
    }
    stack.push(i);
  }

  return answer;
}

Approach: monotonic decreasing stack – maintain a stack of indices with decreasing temperatures. When a warmer day arrives, pop and record the distance for each colder day.

Time: O(n) – each index is pushed and popped at most once.

Space: O(n) – the stack can hold all indices.

#452 Minimum Number of Arrows to Burst Balloons

#901 Online Stock Span