Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Що таке метод «ковзного вікна»?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

## Коротка відповідь

Метод «ковзного вікна» - це техніка двох вказівників (left/right), за якої ми підтримуємо підмасив або підрядок і ефективно оновлюємо відповідь при зсуві меж вікна, уникаючи перерахунку з нуля. Підходить для задач про підрядки/підмасиви, суми/середні, обмеження кількості унікальних елементів, а також пошуку максимумів/мінімумів на відрізках.

## Детально

Ідея: замість того щоб перераховувати значення для кожного підвідрізка заново, ми поступово розширюємо вікно праворуч, а коли умова стає порушеною, зсуваємо ліву межу, підтримуючи допоміжні структури (сума, лічильники частот, дек для максимумів). Це дає лінійну або майже лінійну складність для широкого класу задач.

### Коли застосовувати

- Підрядки/підмасиви, де відповідь залежить від неперервного відрізка.
- Суми/середні за вікном фіксованого розміру k.
- Обмеження на кількість унікальних елементів або частоти символів/чисел.
- Максимум/мінімум на кожному відрізку фіксованої довжини (монотонна черга/дек).
- Задачі «два вказівники» на рядках/масивах з інваріантом вікна.

### Варіанти вікон

- Фіксованого розміру k - підтримуємо метрику (суму/лічильник), додаючи праворуч і прибираючи ліворуч.
- Змінного розміру - розширюємо праву межу, поки умова виконується; якщо порушена, звужуємо ліворуч.
- Монотонне вікно - підтримуємо дек індексів так, щоб значення в ньому спадали/зростали для O(1) доступу до максимуму/мінімуму.

### Загальний шаблон

1. Ініціалізуйте left = 0, пройдіться right від 0 до n-1.
2. Додайте nums[right]/s[right] у вікно, оновіть лічильники/структури.
3. Поки інваріант порушено, зсувайте left, прибираючи елементи й оновлюючи структури.
4. Коли інваріант дотримано, оновлюйте відповідь (максимум/мінімум/довжина/сума).

## Приклади реалізації

### 1) Фіксоване вікно: максимум суми підмасиву довжини k

Задача: повернути максимальну суму будь-якого підмасиву довжини k.

```
function maxSumSubarray(nums, k) {
  if (k > nums.length) return null;
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += nums[i];
  let maxSum = windowSum;
  for (let right = k; right < nums.length; right++) {
    windowSum += nums[right] - nums[right - k];
    if (windowSum > maxSum) maxSum = windowSum;
  }
  return maxSum;
}

console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // 9 (5+1+3)
```

Складність: O(n) за часом, O(1) за пам'яттю.

### 2) Змінне вікно: довжина найдовшого підрядка без повторів

Тримаємо вікно з унікальними символами, зсуваючи left при появі дубліката.

```
function lengthOfLongestSubstring(s) {
  const seen = new Set();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }
    seen.add(s[right]);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

console.log(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")
```

Складність: O(n) за часом, O(алфавіт) за пам'яттю.

### 3) Мінімальний підрядок, що містить усі символи T (Min Window Substring)

Підтримуємо частоти потрібних символів. Розширюємо вікно до виконання умови, потім звужуємо, мінімізуючи довжину.

```
function minWindow(s, t) {
  if (t.length === 0) return "";
  const need = new Map();
  for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1);

let have = 0, required = need.size;
  const window = new Map();
  let left = 0, ans = [-1, 0, 0]; // [len, l, r]

for (let right = 0; right < s.length; right++) {
    const c = s[right];
    window.set(c, (window.get(c) || 0) + 1);
    if (need.has(c) && window.get(c) === need.get(c)) have++;

while (have === required) {
      if (ans[0] === -1 || right - left + 1 < ans[0]) ans = [right - left + 1, left, right];
      const cl = s[left];
      window.set(cl, window.get(cl) - 1);
      if (need.has(cl) && window.get(cl) < need.get(cl)) have--;
      left++;
    }
  }

return ans[0] === -1 ? "" : s.slice(ans[1], ans[2] + 1);
}

console.log(minWindow("ADOBECODEBANC", "ABC")); // "BANC"
```

Складність: O(n) за часом, O(алфавіт) за пам'яттю.

### 4) Максимум у кожному вікні довжини k (монотонна черга/дек)

Зберігаємо індекси в деку так, щоб значення спадали зліва направо. Голова дека - максимум поточного вікна.

```
function maxSlidingWindow(nums, k) {
  const deque = []; // індекси, значення спадають
  const res = [];

for (let i = 0; i < nums.length; i++) {
    // 1) Прибираємо індекси, що вийшли ліворуч
    if (deque.length && deque[0] <= i - k) deque.shift();

// 2) Підтримуємо спадання значень
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }
    deque.push(i);

// 3) Записуємо максимум, коли вікно вже розміру k
    if (i >= k - 1) res.push(nums[deque[0]]);
  }
  return res;
}

console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3)); // [3,3,5,5,6,7]
```

Складність: O(n) за часом, O(k) за пам'яттю (дек).

## Часті помилки і як їх уникнути

- Забути «прибрати» елемент при зсуві left: коректно зменшуйте суму/частоти/очищайте Set.
- Помилки off-by-one: перевіряйте індекси при записі відповіді та межі вікна (right - left + 1).
- Неправильний момент оновлення відповіді: робіть це лише коли інваріант вікна дотримано.
- Спроба сортувати/перебирати заново весь відрізок - ламає лінійність.
- Для максимумів/мінімумів не зберігайте всі елементи вікна - використовуйте монотонний дек.

## Складність і пам'ять

- Фіксоване вікно: O(n) час, O(1) пам'ять.
- Змінне вікно: O(n) час (кожен індекс входить/виходить з вікна не більше разу), O(алфавіт) пам'ять.
- Монотонне вікно (deque): O(n) час, O(k) пам'ять.

## Інтуїція

Думайте про вікно як про «рамку», яку ви плавно переміщуєте: додаєте праворуч, за потреби прибираєте ліворуч, підтримуючи стан так, щоб за O(1) оновлювати відповідь. Це замінює вкладені цикли й перетворює багато задач на лінійні.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати825 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.