Sliding window (suriluvchi oyna): ketma-ket oraliq masalalarini O(n) da yechish

Qisqacha: Suriluvchi oyna — massivning ketma-ket bo'lagi (oralig'i) haqidagi masalalar uchun usul. Har bo'lakni noldan hisoblash o'rniga oyna bir qadam suriladi: o'ngdan bitta element kiradi, chapdan bittasi chiqadi — natija shu ikkitasi bilan yangilanadi. Qat'iy oyna (uzunligi k) — "ketma-ket 3 soatdagi eng katta tushum". O'zgaruvchan oyna — o'ng chet kengayadi, shart buzilsa chap chet torayadi: "takrorsiz eng uzun bo'lak", "summaga yetadigan eng qisqa bo'lak". Ikki chet ham faqat oldinga yurgani uchun vaqt O(n).

Bu darsda

• Qat'iy uzunlikdagi oyna bilan ketma-ket soatlar tushumini O(n · k) o'rniga O(n) da hisoblaysiz.
• O'zgaruvchan oyna bilan "eng qisqa" va "eng uzun" bo'lak masalalarini yechasiz.
• Oyna ichidagi narsalarni Map hisoblagichida saqlab, "takrorsiz" va "ko'pi bilan 2 tur" kabi shartlarni tekshirasiz.
• Masala oyna bilan yechilishini uning so'zlaridan taniysiz.

Oldin bilishingiz kerak: Ikki ko'rsatkich, Map, ?? va ?., Math obyekti.

1. Nega bu kerak?

Jasur aka «Bahor»ga yangi oshpaz olmoqchi, lekin to'liq kunga emas — faqat eng qizg'in uch soatga. Kassa har soat tushumini yozadi: 07:00 dan 23:00 gacha, kuniga 16 ta raqam. Bir oylik ma'lumot bilan savol: ketma-ket qaysi uch soatda tushum eng katta?

Sardorning birinchi yechimi: har soatdan boshlab keyingi uch soatni qo'shish va eng kattasini tanlash. To'g'ri. Lekin Jasur aka "yana 4 soatlikni, 6 soatlikni ham ko'r" desa, har safar ish k baravar ko'payadi. Bir yillik ma'lumotda va "8 soatlik smena" savolida — sezilarli.

Bugungi usul ikki ko'rsatkich g'oyasining davomi. U yerda ikki indeks bir-biriga qarab yoki bir yo'nalishda yurdi. Bugun ham ikkalasi bir yo'nalishda yuradi, lekin biz ularning orasidagi bo'lakka qaraymiz. Bu bo'lak — oyna (window). Poyezd derazasiga o'xshaydi: poyezd yurgan sari derazada bir manzara chiqib ketadi, yangisi kiradi. Butun yo'lni har safar boshidan ko'rish shart emas.

2. Qat'iy oyna

2.1 Sodda yechim

Avval to'g'ri, lekin sekin yechim:

function bestWindowSlow(sales, k) {
  let best = -Infinity;
  for (let start = 0; start + k <= sales.length; start++) {
    let sum = 0;
    for (let i = start; i < start + k; i++) sum += sales[i];
    best = Math.max(best, sum);
  }
  return best;
}

const sales = [120, 340, 560, 410, 180, 620, 700, 250];
console.log(bestWindowSlow(sales, 3)); // 1570

Tashqi sikl n − k + 1 marta, ichki — k marta. Vaqt — O((n − k + 1) · k), qisqacha O(n · k). k kichik bo'lsa — deyarli O(n). k n ning yarmi bo'lsa — O(n²) ga yaqin.

2.2 G'oya: qo'shnilar umumiy qismni bo'lishadi

07:00–10:00 oynasi va 08:00–11:00 oynasini solishtiring. Ikkalasida 08:00 va 09:00 soatlari bor. Farq — faqat ikki chetda: birinchisida 07:00 ortiqcha, ikkinchisida 10:00. Demak, yangi yig'indini noldan hisoblash shart emas:

yangi yig'indi = eski yig'indi + kirgan soat − chiqqan soat

Oyna qanday surilishini kuzating. Bo'yalgan kataklar — joriy oyna:

Birinchi oyna k ta qo'shish oldi. Keyin har surish — ikki amal: qo'shish va ayirish. Jami k + 2 · (n − k) — O(n), k qancha bo'lmasin. Xotira — bir nechta son, O(1).

2.3 O'lchov: k o'sganda

100 000 soatlik ma'lumotda (taxminan 17 yil) oyna uzunligini oshirib bordik. Har k alohida jarayonda, 7 o'lchov medianasi:

Sodda yechimda k ikki baravar — vaqt ham ikki baravar: O(n · k) da n o'zgarmas, k o'sdi. Suriluvchi oynada vaqt k ga bog'liq emas — taxminan 0,4 ms. 800 soatlik oynada farq 120 baravar.

Tekshirib ko'ring: Tushumlar [200, 500, 300, 900], k = 2. Oyna har surishda qanday yangilanadi va javob qancha?

2.4 Qaysi qiymatni oynada yangilash oson?

Yig'indi bilan hammasi silliq chiqdi, chunki chiqqan soatni ayirib tashlash mumkin. Endi Jasur akaning boshqa savolini olaylik: "Har 3 soatlik oynada eng qimmat soat qancha bo'lgan?" Bu yerda muammo bor.

Oyna [560, 410, 180] bo'lsin, eng kattasi — 560. Oyna suriladi: 560 chiqadi, 620 kiradi. Yangi eng katta qancha? 620 — bu oson. Lekin 620 o'rniga 300 kirsa-chi? Unda eng katta — 410. Buni bilish uchun qolgan elementlarni qayta ko'rish kerak. "Maksimumdan ayirish" degan amal yo'q.

Demak, qiymatlar ikki turga bo'linadi:

Eng katta va eng kichik uchun ham O(n) yechim bor. U oynada "nomzodlar" navbatini maxsus tartibda saqlaydi — monoton navbat. Uni Monotonic stack va queue darsida quramiz. Hozircha qoida: oyna usulini tanlashdan oldin "chiqib ketgan elementni natijadan qanday olib tashlayman?" deb so'rang. Javob tez bo'lsa — oyna O(n).

3. O'zgaruvchan oyna: eng qisqa bo'lak

3.1 Masala

Jasur aka yangi savol berdi: "Kunlik reja — 1 000 000 so'm. Ketma-ket eng kam nechta soatda bunga yetamiz?" Endi oyna uzunligi oldindan ma'lum emas — uni topish kerak.

Sodda yo'l — har boshlanishdan yig'ib borish, yetganda to'xtash: O(n²). Oyna bilan esa ikki qoida:

1. Yig'indi yetmasa — oynani o'ngga kengaytiramiz (right++, soat qo'shiladi).
2. Yig'indi yetsa — natijani yozamiz va oynani chapdan toraytiramiz (left++, soat ayriladi). Balki kamroq soat ham yetar?

function shortestToTarget(sales, target) {
  let left = 0;
  let sum = 0;
  let best = Infinity;
  for (let right = 0; right < sales.length; right++) {
    sum += sales[right]; // o'ng chet kengayadi
    while (sum >= target) {
      best = Math.min(best, right - left + 1);
      sum -= sales[left]; // chap chet torayadi
      left++;
    }
  }
  return best === Infinity ? 0 : best;
}

const sales = [120, 340, 560, 410, 180, 620, 700, 250]; // ming so'm
console.log(shortestToTarget(sales, 1000)); // 2
console.log(shortestToTarget(sales, 1500)); // 3
console.log(shortestToTarget(sales, 99999)); // 0

Infinity — "hali topilmadi" belgisi: har qanday haqiqiy uzunlik undan kichik. Oxirida u qolsa — reja hech qachon bajarilmagan, 0 qaytaramiz.

3.2 Nega bu O(n)?

Ichida while bor — yana O(n²) emasmi? Yo'q. Sanash usulini o'zgartiramiz: siklni emas, ko'rsatkichlar yurishini sanaymiz. right jami n marta oldinga yuradi. left ham jami ko'pi bilan n marta — u hech qachon orqaga qaytmaydi va right dan o'tib ketmaydi. Ikkalasi birga ko'pi bilan 2n qadam: O(n). Ichki while ba'zan ko'p, ba'zan nol marta aylanadi, lekin jami chegaralangan — xuddi amortizatsiya kabi.

Diqqat: Bu usul faqat manfiy bo'lmagan sonlarda ishlaydi. Unda oynani toraytirish yig'indini doim kamaytiradi, kengaytirish — oshiradi. Agar orada manfiy son (masalan, qaytarilgan pul) bo'lsa, toraytirish yig'indini oshirib yuborishi mumkin va mantiq buziladi. Manfiy sonli "yig'indi = k" masalalari Prefix sum darsida boshqa usul bilan yechiladi.

Tekshirib ko'ring: Tushumlar [500, 600], reja 1 000. shortestToTarget qadamma-qadam nima qiladi va nima qaytaradi?

4. Takrorsiz eng uzun bo'lak

4.1 Masala

«Bahor»da "Tatib ko'ring" aksiyasi: mehmon ketma-ket buyurtma qilgan taomlar ichida takrorsiz eng uzun bo'lak qancha? Masalan: osh, manti, norin, osh, ... — ikkinchi "osh" kelgan joyda takror boshlanadi.

Oyna g'oyasi: oyna doim takrorsiz. O'ng chetdan yangi taom kiradi. Agar u oynada allaqachon bo'lsa — chap chetni eski nusxasidan keyinga sakratamiz. Eski nusxa qayerdaligini bilish uchun Map ishlatamiz: taom → oxirgi ko'rilgan indeksi. Pastdagi "o'zgaruvchilar" qismida shu Map ni kuzating:

Ikki tuzoqqa qarang. Birinchisi — prev >= left sharti. "Norin" oxirida ikkinchi marta kelganda, uning eski nusxasi (indeks 2) hali oynada edi — sakradik. Agar eski nusxa oynadan tashqarida qolgan bo'lsa (prev < left), u endi takror emas. Bu shartsiz left orqaga qaytib ketishi mumkin edi. Ikkinchisi — left sakrashi: bitta-bitta emas, darhol kerakli joyga. Bu faqat tezlik uchun; bitta-bitta yurganda ham O(n) bo'lardi.

4.2 O'lchov

Bu masalaning sodda yechimi — har boshlanishdan takror topilguncha yurish. Uning narxi O(n · m), m — takrorsiz bo'lakning o'rtacha uzunligi. Bizning sinovda 5 000 xil "taom" bor edi va bo'laklar uzun chiqmadi, shuning uchun sodda yechim ham chiziqli o'sdi — lekin ancha sekin:

Ikkalasi ham n bilan ikki baravar o'sdi, lekin oyna 100 baravar tez. Sababi — m: sodda yechim har boshlanishda ~90 ta elementni qayta ko'rdi va har safar yangi Set yasadi. Takrorlar kam bo'lsa (m katta), sodda yechim kvadratikka yaqinlashadi. Oyna esa doim O(n).

5. Oynada hisoblagich: "ko'pi bilan 2 tur"

Oshxonada ikkita katta qozon bor. Oshpaz ketma-ket buyurtmalarni faqat ikki xil taom bo'lsa, birga tayyorlay oladi. Eng uzun shunday bo'lak qancha?

Bu safar "oxirgi indeks" yetmaydi: oynadan bitta taom chiqqanda, uning boshqa nusxalari oynada qolishi mumkin. Shuning uchun Map da hisoblagich saqlaymiz: taom → oynada nechta. Hisob nolga tushsa — kalitni o'chiramiz. Shunda count.size — oynadagi turli taomlar soni:

function longestTwoKinds(dishes) {
  const count = new Map(); // taom → oynada nechta
  let left = 0;
  let best = 0;
  for (let right = 0; right < dishes.length; right++) {
    const dish = dishes[right];
    count.set(dish, (count.get(dish) ?? 0) + 1);
    while (count.size > 2) {
      const out = dishes[left]; // chap chetdagi chiqadi
      count.set(out, count.get(out) - 1);
      if (count.get(out) === 0) count.delete(out);
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

const orders = ["osh", "manti", "osh", "norin",
  "norin", "osh", "norin", "manti"];
console.log(longestTwoKinds(orders)); // 5
console.log(longestTwoKinds([]), longestTwoKinds(["osh"])); // 0 1

Javob 5: "osh, norin, norin, osh, norin". count.get(dish) ?? 0 — taom hali yo'q bo'lsa 0 dan boshlaymiz (?? operatori). Vaqt — O(n), yana har chet faqat oldinga. Xotira — oynadagi turli taomlar: bu yerda ko'pi bilan 3 ta kalit, O(1). Umumiy holda "ko'pi bilan k tur" — O(k).

Bu shablon ko'p masalaga mos: "oynada ko'pi bilan k ta turli belgi", "oyna qatorning hamma harflarini o'z ichiga oladimi", "anagramma qaysi joyda". Har safar faqat ikki narsa o'zgaradi: oyna shartini nima buzadi va natijani qachon yozamiz.

Tekshirib ko'ring: Nega bu yerda if emas, while (count.size > 2) ishlatildi?

6. Masalani qanday taniysiz

Oyna usuliga ishora beradigan so'zlar:

• "ketma-ket k ta", "uzluksiz bo'lak (subarray, substring)", "ketma-ket kunlar/soatlar";
• "eng uzun / eng qisqa bo'lak, unda ...";
• "ko'pi bilan k ta turli", "takrorsiz", "hamma ... ni o'z ichiga oladigan".

Ikki muhim shart:

1. Ketma-ketlik. "Istalgan k ta taom" — oyna emas (bu tanlash yoki saralash). Oyna faqat yonma-yon turgan elementlar uchun.
2. Monotonlik. Oynani kengaytirish shartni faqat bir tomonga o'zgartirishi kerak: yig'indi oshadi, turlar ko'payadi. Shunda "shart buzildi — toraytir" mantiqi ishlaydi. Manfiy sonlar bilan yig'indi masalasida bu buziladi.

7. Chegaraviy holatlar

• k > n. Oyna sig'maydi. bestWindow da birinchi sikl sales[i] ni massivdan tashqarida o'qiydi — undefined qo'shiladi va natija NaN. Oldindan tekshiring: if (k > sales.length) return null.
• k = 0 yoki bo'sh massiv. Javob nima bo'lishini shartda kelishib oling (0 yoki null) va testga yozing.
• Hamma elementlar bir xil. Takrorsiz bo'lak — 1. "Ko'pi bilan 2 tur" — butun massiv.
• Hech qachon yetmaydi. shortestToTarget — Infinity belgisi va 0 qaytarish.
• Manfiy sonlar. O'zgaruvchan yig'indi oynasi ishlamaydi; qat'iy oyna esa ishlaydi — u faqat qo'shish va ayirishdan foydalanadi.

8. Ko'p uchraydigan xatolar

8.1 Har surishda oynani qayta qo'shish

sales.slice(i, i + k).reduce(...) — chiroyli, lekin har surishda k ta element nusxalanadi va qo'shiladi: O(n · k) (JS amallarining narxi). Tuzatish: bitta sum o'zgaruvchisi, + kirgan − chiqqan.

8.2 Bir xato bilan indeks (off-by-one)

Oyna uzunligi — right - left + 1, right - left emas. Chiqayotgan element — sales[right - k]. Tuzatish: 3–4 elementli misolni qo'lda yuring.

8.3 Eski nusxani tekshirmaslik

longestDistinct da prev >= left siz left orqaga qaytadi va javob katta chiqadi. Tuzatish: "u hali oynadami?" deb so'rang.

8.4 Nolga tushgan kalitni o'chirmaslik

count.size turli taomlarni sanaydi, faqat hisobi 0 bo'lganlar o'chirilsa. Tuzatish: if (count.get(out) === 0) count.delete(out).

9. Mashqlar

1-mashq (oson): Qo'lda suring

Tushumlar [300, 100, 400, 200, 600], k = 2. Har oyna yig'indisini sodda usulda va surish usulida yozing. Surishda nechta qo'shish/ayirish bo'ldi?

2-mashq (o'rta): O'rtacha kutish

Kuryer yetkazish vaqtlari (daqiqa) ketma-ket yozilgan. Ketma-ket 3 ta yetkazishning o'rtachasi 40 daqiqadan oshgan oynalar sonini qaytaradigan countSlowWindows(times, k, limit) ni O(n) da yozing. [30, 45, 50, 20, 60, 55], k = 3, limit 40 → 3.

Ishora: o'rtacha > limit ↔ yig'indi > limit × k. Bo'lishni har safar qilmang.

function countSlowWindows(times, k, limit) {
  if (k > times.length || k <= 0) return 0;
  let sum = 0;
  for (let i = 0; i < k; i++) sum += times[i];
  let count = sum > limit * k ? 1 : 0;
  for (let right = k; right < times.length; right++) {
    sum += times[right] - times[right - k];
    if (sum > limit * k) count++;
  }
  return count;
}

console.log(countSlowWindows([30, 45, 50, 20, 60, 55], 3, 40)); // 3
console.log(countSlowWindows([30, 45], 3, 40)); // 0

3-mashq (qiyin): Oyna funksiyalari testlari

kurs/mashqlar/14/08-oyna/oyna.test.mjs faylida darsdagi bestWindow, longestDistinct va longestTwoKinds ni yozing. bestWindow ga k > n tekshiruvini qo'shing (null qaytarsin). Testlar (node:test):

1. bestWindow — darsdagi misol { best: 1570, bestStart: 5 }; k > n → null; manfiy sonlar bilan to'g'ri.
2. longestDistinct — bo'sh → 0, hammasi bir xil → 1, hammasi turli → n.
3. 300 ta urug'li tasodifiy ro'yxatda (uzunligi 0–40, 4 xil taom) longestDistinct va longestTwoKinds sodda yechimlar bilan bir xil. Sodda yechim: har boshlanishdan Set bilan yurish.

// kurs/mashqlar/14/08-oyna/oyna.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

function bestWindow(sales, k) {
  if (k <= 0 || k > sales.length) return null;
  let sum = 0;
  for (let i = 0; i < k; i++) sum += sales[i];
  let best = sum;
  let bestStart = 0;
  for (let right = k; right < sales.length; right++) {
    sum += sales[right] - sales[right - k];
    if (sum > best) {
      best = sum;
      bestStart = right - k + 1;
    }
  }
  return { best, bestStart };
}

function longestDistinct(items) {
  const lastSeen = new Map();
  let left = 0;
  let best = 0;
  for (let right = 0; right < items.length; right++) {
    const prev = lastSeen.get(items[right]);
    if (prev !== undefined && prev >= left) left = prev + 1;
    lastSeen.set(items[right], right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

function longestTwoKinds(items) {
  const count = new Map();
  let left = 0;
  let best = 0;
  for (let right = 0; right < items.length; right++) {
    count.set(items[right], (count.get(items[right]) ?? 0) + 1);
    while (count.size > 2) {
      const out = items[left++];
      count.set(out, count.get(out) - 1);
      if (count.get(out) === 0) count.delete(out);
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

// sodda yechim: har boshlanishdan, turlar soni maxKinds dan oshguncha
function slowLongest(items, maxKinds, distinct) {
  let best = 0;
  for (let start = 0; start < items.length; start++) {
    const seen = new Map();
    for (let end = start; end < items.length; end++) {
      const c = (seen.get(items[end]) ?? 0) + 1;
      if (distinct && c > 1) break;
      seen.set(items[end], c);
      if (seen.size > maxKinds) break;
      best = Math.max(best, end - start + 1);
    }
  }
  return best;
}

function makeRandom(seed) {
  return () => (seed = (seed * 16807) % 2147483647);
}

test("bestWindow — misol, k > n, manfiy", () => {
  const sales = [120, 340, 560, 410, 180, 620, 700, 250];
  const expected = { best: 1570, bestStart: 5 };
  assert.deepEqual(bestWindow(sales, 3), expected);
  assert.equal(bestWindow([1, 2], 3), null);
  const negative = bestWindow([-5, -1, -3], 2);
  assert.deepEqual(negative, { best: -4, bestStart: 1 });
});

test("longestDistinct — chegaralar", () => {
  assert.equal(longestDistinct([]), 0);
  assert.equal(longestDistinct(["osh", "osh", "osh"]), 1);
  assert.equal(longestDistinct(["osh", "manti", "norin"]), 3);
});

test("sodda yechimlar bilan bir xil", () => {
  const random = makeRandom(2026);
  const kinds = ["osh", "manti", "norin", "somsa"];
  for (let k = 0; k < 300; k++) {
    const n = random() % 41;
    const items = Array.from(
      { length: n },
      () => kinds[random() % 4],
    );
    assert.equal(longestDistinct(items), slowLongest(items, n, true));
    const two = slowLongest(items, 2, false);
    assert.equal(longestTwoKinds(items), two);
  }
});

✔ bestWindow — misol, k > n, manfiy (1.278ms)
✔ longestDistinct — chegaralar (0.1672ms)
✔ sodda yechimlar bilan bir xil (6.4688ms)
ℹ tests 3
ℹ suites 0
ℹ pass 3
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 125.0671

4-mashq: Amaliy tajriba — "Oyna" qatorlari

kurs/mashqlar/14/MURAKKABLIK.md ga bugungi to'rt yechimni "Naqsh" ustuni bilan qo'shing. "Xotira" ustunida Map ning hajmi nimaga bog'liqligini yozing.

| Masala | Naqsh | Vaqt | Xotira |
|---|---|---|---|
| k soatlik eng katta tushum | qat'iy oyna | O(n) | O(1) |
| Rejaga yetadigan eng qisqa bo'lak | o'zgaruvchan oyna | O(n) | O(1) |
| Takrorsiz eng uzun bo'lak | o'zgaruvchan oyna + Map | O(n) | O(turli taomlar) |
| Ko'pi bilan 2 tur | oyna + Map hisoblagich | O(n) | O(1) — ≤ 3 kalit |

git add 14/MURAKKABLIK.md 14/08-oyna
git commit -m "14/08: suriluvchi oyna, sodda yechim bilan testlar"

10. Real ishda

• Monitoring va analitika. "Oxirgi 5 daqiqadagi so'rovlar", "oxirgi 7 kunning o'rtacha tushumi" (moving average) — grafiklardagi silliq chiziq aynan suriluvchi oyna bilan hisoblanadi.
• Rate limiting. Server "daqiqasiga 120 so'rov" cheklovini oyna bilan tekshiradi: oxirgi 60 soniyadagi so'rovlar soni (Debounce va throttle darsidagi cheklovning server tomoni).
• Tarmoq protokollari. TCP ma'lumot yuborishda "sliding window" ishlatadi — tasdiqlanmagan paketlar oynasi.
• Intervyu. LeetCode'dagi "Maximum Average Subarray I", "Minimum Size Subarray Sum", "Longest Substring Without Repeating Characters", "Fruit Into Baskets" — bugungi to'rt masalaning asl nomlari. Oxirgisi aynan "ko'pi bilan 2 tur".

Xulosa

• Suriluvchi oyna — ketma-ket bo'lak masalalari uchun: har surishda bitta kiradi, bitta chiqadi.
• Qat'iy oyna — O(n), k ga bog'liq emas: 100 000 soatda 800 soatlik oyna sodda usulda 50 ms, oyna bilan 0,4 ms oldi.
• O'zgaruvchan oyna — o'ng chet kengayadi, shart buzilsa chap chet torayadi. Ikkalasi faqat oldinga — jami O(n).
• Oyna ichidagi narsalar Map da: "oxirgi indeks" (takrorsiz) yoki "hisoblagich" (ko'pi bilan k tur).
• Shartlar: elementlar ketma-ket bo'lsin va kengaytirish shartni bir tomonga o'zgartirsin; yig'indi oynasida manfiy sonlar bo'lmasin.

Keyingi dars: Prefix sum va difference array — yig'indilarni oldindan hisoblab, istalgan oraliq yig'indisini O(1) da olish va manfiy sonli "yig'indi = k" masalasini yechish.

Manbalar

• LeetCode masalalari: "Maximum Average Subarray I", "Minimum Size Subarray Sum", "Longest Substring Without Repeating Characters", "Fruit Into Baskets" — leetcode.com (shartlar bu yerda o'zgartirib berilgan)
• Steven S. Skiena, "The Algorithm Design Manual", 3-nashr, Springer, 2020
• MDN: Map — developer.mozilla.org