Kuyruk ve Deque

Nasıl düşünülür

Kuyruk varış sırasını korur. Monoton deque pencere min/maks aday indekslerini tutar: ön her zaman cevap; arka ezilen değerleri atar. Kayar pencereyle her indeks bir girer bir çıkar.

Şablon şekilleri

Şekil	Temel hamle	Notlar
FIFO kuyruk	Enqueue / dequeue	BFS, tampon
Monoton deque	Daha kötüyse arkadan pop	Pencere max/min
Zaman penceresi	Süresi dolanı önden at	Vuruş sayacı

Karmaşıklık temeli

Pencere ekstremum için amortize O(n); basit kuyruk tasarımlarında işlem başına O(1).

Şablondan probleme

1. İki uç gerekip gerekmediğine göre queue vs deque seç.
2. Pencere max için deque’de azalan değerleri koru.
3. Pencereden çıktıysa önü at; arkayı temizledikten sonra yeni indeksi push et.
4. Pencere dolduktan sonra önü kaydet.

/** Deque template: sliding window maximum. */
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;
}

/** Deque template: sliding window maximum. */
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;
}