Що таке метод «ковзного вікна»?

АлгоритмиJunior~2 хв читання

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

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

Детально

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

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

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

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

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

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

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

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

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) оновлювати відповідь. Це замінює вкладені цикли й перетворює багато задач на лінійні.

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

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.