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

Hardqueue-deque

Sliding Window Maximum

Problem (yeniden ifade)

Bir nums dizisi ve pencere boyu k verilir. Pencereyi soldan sağa kaydır ve her penceredeki maksimum değerin dizisini döndür.

Sezgi

Kaba kuvvet her pencereyi yeniden tarar. Optimal fikir: max adaylarını azalan indeks deque’sinde tut. Ön her zaman mevcut max. Pencereden çıkan indeksleri at; pencerede hâlâ daha büyük bir değer varken max olamayacak arka değerleri at.

Yaklaşımlar

Monoton deque

Doğrulanmadı

Zaman O(n)Alan O(k)

Fikir. Deque azalan nums değerleriyle indeksler tutar. Her i için: (1) ≤ i-k ise önden pop, (2) nums[back] ≤ nums[i] iken arkadan pop, (3) i push, (4) i ≥ k-1 ise nums[front] üret.

Yürüyüş. nums = [1,3,-1,-3,5,3,6,7], k = 3 → [3,3,5,5,6,7]. 5 gelince deque’yi temizler; ön her zaman canlı pencerenin cevabıdır.

Trade-off. Her indeks bir kez girer/çıkar → O(n). Kaba kuvvete göre icat etmesi daha zor, ama beklenen hard çözüm bu.

Çözüm

export function maxSlidingWindow(nums: number[], k: number): number[] {
  const dq: number[] = [];
  const res: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    while (dq.length && dq[0]! <= i - k) dq.shift();
    while (dq.length && nums[dq[dq.length - 1]!]! <= nums[i]!) dq.pop();
    dq.push(i);
    if (i >= k - 1) res.push(nums[dq[0]!]!);
  }
  return res;
}

export function maxSlidingWindow(nums: number[], k: number): number[] {
  const dq: number[] = [];
  const res: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    while (dq.length && dq[0]! <= i - k) dq.shift();
    while (dq.length && nums[dq[dq.length - 1]!]! <= nums[i]!) dq.pop();
    dq.push(i);
    if (i >= k - 1) res.push(nums[dq[0]!]!);
  }
  return res;
}

Pencere başına kaba kuvvet

Doğrulanmadı

Zaman O(n·k)Alan O(1)

Fikir. Her pencere başlangıcında max için k elemanı tara.

Yürüyüş. Aynı girdi: doğru ama en kötü durumda karesel (k ≈ n/2).

Trade-off. Yalnızca doğrulama veya çok küçük k için. Mülakatlar n büyük olunca deque ister.

Çözüm

/** O(n*k) scan each window, baseline to beat with the deque. */
export function maxSlidingWindowBrute(nums: number[], k: number): number[] {
  const res: number[] = [];
  for (let i = 0; i <= nums.length - k; i++) {
    let m = -Infinity;
    for (let j = i; j < i + k; j++) m = Math.max(m, nums[j]!);
    res.push(m);
  }
  return res;
}

/** O(n*k) scan each window, baseline to beat with the deque. */
export function maxSlidingWindowBrute(nums: number[], k: number): number[] {
  const res: number[] = [];
  for (let i = 0; i <= nums.length - k; i++) {
    let m = -Infinity;
    for (let j = i; j < i + k; j++) m = Math.max(m, nums[j]!);
    res.push(m);
  }
  return res;
}

Şablon bağlantısı

Kuyruk ve deque pencere ekstremumları: monoton deque şablonu.

Yaygın hatalar

İndeks yerine değer saklamak (önün pencereden çıkıp çıkmadığını bilemezsin).
index <= i - k iken önden pop etmeyi unutmak.
Azalmayan deque kullanmak (max için kesinlikle azalan olmalı).

Yansıma

Neden değer değil indeks saklanır?
Önden i - k’yı atmayı unutursan ne bozulur?