Daily Temperatures

Problem (yeniden ifade)

Günlük sıcaklıklar verilir; answer[i], i. günden sonra daha sıcak bir güne kaç gün bekleneceğini tutar. Yoksa answer[i]=0.

Sezgi

Sonraki daha büyük eleman → indekslerin monoton azalan yığını. Daha sıcak gün gelince pop edip mesafeyi yaz.

Yaklaşımlar

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;
}

Şablon bağlantısı

Monoton yığın sonraki-daha-büyük şablonu.

Yansıma

• Daha sıcak gün gelince yığındaki günlerin cevabı i - idx. Yığında indeks durur, sıcaklık değil.
• Eşit sıcaklık daha sıcak sayılmaz. > ile >= hangi günü erken kapatır?
• Sonda kalanlar 0. Azalan dizi hepsi 0. Artan dizi her gün 1.