Что такое скользящее окно — приём, который считает «лучшую неделю» за один проход

Задача из жизни: у тебя продажи по дням за год, 365 чисел. Найди лучшую неделю — семь дней подряд с самой большой суммой.

Первое решение, которое приходит в голову, честное и рабочее:

let best = -Infinity;
for (let i = 0; i + 7 <= sales.length; i++) {
  let sum = 0;
  for (let j = i; j < i + 7; j++) sum += sales[j];
  best = Math.max(best, sum);
}

359 недель, в каждой 7 сложений — около 2 500 операций. Терпимо. А теперь «лучший месяц за 10 лет»: 3 650 дней, окно 30. Уже больше 100 000 сложений. И почти все — повторы: соседние месяцы делят 29 одних и тех же дней.

Вот хитрость: эти 29 дней пересчитывать не нужно вообще.

Что такое скользящее окно простыми словами

Скользящее окно — это кусок массива подряд, который едет по данным. На каждом шаге окно сдвигается на одну позицию: один элемент входит справа, один выходит слева.

Представь деревянную рамку на длинном ряду плиток. Сдвинул рамку на одну плитку — внутри изменились ровно две: новая справа и ушедшая слева. Всё остальное то же самое. Значит, и сумму можно не считать заново, а поправить: прибавить вошедшее, вычесть ушедшее.

Как это работает

let sum = 0;
for (let i = 0; i < 7; i++) sum += sales[i];  // первое окно — честно
let best = sum;

for (let i = 7; i < sales.length; i++) {
  sum += sales[i] - sales[i - 7];  // вошёл день i, ушёл день i-7
  best = Math.max(best, sum);
}

Один цикл вместо двух. На каждом шаге — одно сложение и одно вычитание, какого бы размера ни было окно. Для недели, месяца или года — одинаково около 2 операций на день. 10 лет с окном 30 — это примерно 7 000 операций вместо 100 000.

Это окно фиксированного размера. Есть второй вид — гибкое окно. Его края двигаются по отдельности: правый расширяет, левый сжимает, пока условие снова не выполнится.

Пример: найти самый длинный кусок строки без повторяющихся букв.

function longestUnique(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++]);  // сжимаем слева
    seen.add(s[right]);                                 // расширяем справа
    best = Math.max(best, right - left + 1);
  }
  return best;
}

longestUnique("абракадабра"); // 4 — «дабр»

Попробуй найти это глазами — неприятно: «бра», «рак» и «кад» по три буквы, и легко пропустить «дабр» у самого конца. А алгоритм не устаёт: каждая буква входит в окно один раз и выходит не больше одного раза.

Зачем это тебе

• Узнавать приём в задачах. Слова «подряд», «последние N», «самый длинный кусок, где…» — почти всегда скользящее окно. Если видишь вложенный цикл по соседним элементам — проверь, не пересчитываешь ли ты одно и то же.
• Графики и метрики. «Среднее за последние 7 дней» на дашборде — это окно. Его часто хранят в кольцевом буфере: новый замер затирает самый старый.
• Лимиты запросов. Тут разница видна особенно ярко.

Где ты его встретишь: лимиты запросов

Допустим, API разрешает 100 запросов в минуту. Простейший rate limit — фиксированное окно: счётчик обнуляется в начале каждой минуты.

Подвох: клиент шлёт 100 запросов в 10:00:59 и ещё 100 в 10:01:00. Оба окна довольны. А сервер за две секунды получил 200 запросов — вдвое больше лимита.

Скользящее окно смотрит на «последние 60 секунд» от текущего момента, а не на календарную минуту. Тогда в 10:01:00 оно видит все 100 запросов из прошлой секунды и новые не пропускает. Граница минуты больше не дырявая.

Поэтому в библиотеках лимитов ты встретишь варианты fixed window и sliding window. Второй чуть дороже, зато без всплеска на стыке.

Чем скользящее окно отличается от двух указателей?

Гибкое окно — частный случай приёма «два указателя»: левый и правый края двигаются в одну сторону. У окна фиксированного размера указатель по сути один — второй всегда отстаёт на k.

Работает ли окно, если в массиве есть отрицательные числа?

Для суммы фиксированного окна — да, ничего не ломается. А вот гибкое окно «сжимай, пока сумма больше X» на отрицательных числах врёт: сжатие может сумму увеличить. Там нужны префиксные суммы.

Как сделать скользящее окно в SQL?

Через оконные функции: SUM(amount) OVER (ORDER BY day ROWS BETWEEN 6 PRECEDING AND CURRENT ROW) даёт сумму за семь дней на каждой строке. База сама двигает окно.