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

Easymonotonic-stack

Next Greater Element I

Problem (yeniden ifade)

nums1, nums2’nin alt kümesi. nums1’deki her x değeri için, nums2’de x’in sağındaki ilk katı daha büyük elemanı bul. Yoksa cevap -1.

Sezgi

nums2’deki her değer için azalan monoton yığınla sonraki-daha-büyüğü önceden hesapla, sonuçları bir map’te tut, sonra her nums1 değerine bak.

Yaklaşımlar

nums2 üzerinde monoton yığın + map

Doğrulanmadı

Zaman O(n + m)Alan O(n)

Fikir. nums2’yi soldan sağa tara. Yığın, daha büyük bir halef bekleyen değerleri tutar. x tepeyi yendiğinde, tepe → x map’le. Çözülmeyen değerler kayıtsız kalır (cevap -1).

Yürüyüş. nums2 = [1,3,4,2], nums1 = [4,1,2] → next map: 1→3, 3→4 → cevaplar [-1, 3, -1].

Trade-off. nums2’deki değerler benzersiz, bu yüzden değere göre anahtarlanan map güvenli. Konum gerektiğinde indeks tabanlı yığın eşdeğer.

Çözüm

export function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  const next = new Map<number, number>();
  const stack: number[] = [];
  for (const x of nums2) {
    while (stack.length && stack[stack.length - 1]! < x) {
      next.set(stack.pop()!, x);
    }
    stack.push(x);
  }
  return nums1.map((x) => next.get(x) ?? -1);
}

export function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  const next = new Map<number, number>();
  const stack: number[] = [];
  for (const x of nums2) {
    while (stack.length && stack[stack.length - 1]! < x) {
      next.set(stack.pop()!, x);
    }
    stack.push(x);
  }
  return nums1.map((x) => next.get(x) ?? -1);
}

Şablon bağlantısı

Klasik sağdaki-sonraki-daha-büyük. Daily Temperatures ile aynı yığın disiplini; çıktı mesafe değil, daha büyük değer.

Yansıma

nums2’de azalan adaylar yığında. Daha büyük gelince yığın boşalır ve map dolar. nums1 yalnızca map’e bakar.
Son elemanın sonraki büyüğü neden −1? nums1’de olup nums2’de eşi olmayan yok (garanti).
Yinelenen değer garantisi kalkarsa anahtar değer değil indeks olmalı.