Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediummonotonic-stack

Next Greater Element II

Problem (yeniden ifade)

Dairesel dizi: her i indeksi için, bir kez dolanarak sağdaki sonraki katı daha büyük elemanı bul. Yoksa -1.

Sezgi

Doğrusal sonraki-daha-büyük ile aynı azalan yığın, ama diziyi iki kez yürü (i % n ile 2n adım) ki dolanma adayları önceki indeksleri çözebilsin.

Yaklaşımlar

Dairesel sonraki-daha-büyük (2n tarama)

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. İndeks yığını, değere göre azalan. Her adımda mevcut daha büyükken pop et ve ans[popped] = nums[i] yaz. Her indeks en fazla bir kez beklesin diye yalnızca ilk geçişte push et.

Yürüyüş. [1,2,1] → indeks 2 (değer 1) için dolanınca 2 bulunur → [2,-1,2].

Trade-off. Hâlâ O(n): her indeks bir kez push, en fazla bir kez pop. İkinci geçişte push gereksizdir ve dikkat edilmezse cevapları bozabilir.

Çözüm

export function nextGreaterElements(nums: number[]): number[] {
  const n = nums.length;
  const ans = new Array<number>(n).fill(-1);
  const stack: number[] = [];
  for (let k = 0; k < 2 * n; k++) {
    const i = k % n;
    while (stack.length && nums[i]! > nums[stack[stack.length - 1]!]!) {
      ans[stack.pop()!] = nums[i]!;
    }
    if (k < n) stack.push(i);
  }
  return ans;
}

export function nextGreaterElements(nums: number[]): number[] {
  const n = nums.length;
  const ans = new Array<number>(n).fill(-1);
  const stack: number[] = [];
  for (let k = 0; k < 2 * n; k++) {
    const i = k % n;
    while (stack.length && nums[i]! > nums[stack[stack.length - 1]!]!) {
      ans[stack.pop()!] = nums[i]!;
    }
    if (k < n) stack.push(i);
  }
  return ans;
}

Şablon bağlantısı

Sonraki-daha-büyük şablonu + dairesel sanal uzunluk. NGE I (496) ve Daily Temperatures (739) ile eşleştir.

Yansıma

Döngü için tarama 2n. Yığın hâlâ indeks tutar; değer nums[i % n].
i >= n iken yalnızca cevap yazarsın. İkinci turda kendinden küçükleri neden tekrar itmezsin?
Tamamen azalan dizi: hepsi −1. Tek eleman −1.