Daily Temperatures

Problem (restated)

Given daily temperatures, return an array answer where answer[i] is the number of days you wait after day i for a warmer temperature. If none, answer[i]=0.

Intuition

Next greater element → monotonic decreasing stack of indices. When a warmer day appears, pop and record distance.

Approaches

export function dailyTemperatures(temperatures: number[]): number[] {
  const n = temperatures.length;
  const ans = new Array<number>(n).fill(0);
  const stack: number[] = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && temperatures[i]! > temperatures[stack[stack.length - 1]!]!) {
      const j = stack.pop()!;
      ans[j] = i - j;
    }
    stack.push(i);
  }
  return ans;
}

export function dailyTemperatures(temperatures: number[]): number[] {
  const n = temperatures.length;
  const ans = new Array<number>(n).fill(0);
  const stack: number[] = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && temperatures[i]! > temperatures[stack[stack.length - 1]!]!) {
      const j = stack.pop()!;
      ans[j] = i - j;
    }
    stack.push(i);
  }
  return ans;
}

Template connection

Monotonic stack next-greater template.

Reflection

• When a warmer day arrives, each day on the stack gets i - idx. The stack stores the index, not the temperature.
• An equal temperature is not warmer. Which day does > close that >= would leave open?
• Whatever is left at the end is 0. A decreasing row is all 0s. An increasing row is 1 for every day.