Скользящее окно
Окно фиксированной ширины скользит по массиву: вместо пересчёта — вычесть уходящее, прибавить входящее.
1function maxWindowSum(arr: number[], k: number): number {2 let sum = 03 for (let i = 0; i < k; i++) sum += arr[i]4 5 let best = sum6 for (let i = k; i < arr.length; i++) {7 sum += arr[i] - arr[i - k]8 best = Math.max(best, sum)9 }10 11 return best12}Проблема
Найти максимум суммы k подряд идущих элементов. Наивно — просуммировать каждое окно заново: O(n·k). Окно учитывает инвариант: соседние окна отличаются ровно двумя элементами.
Что вы видите
Рамка «окно» на k ячейках. Сдвиг: левая ячейка гаснет и вычитается, правая вспыхивает и прибавляется — новая сумма за O(1). Лучшее окно запоминается подписью.
Как это работает
Сумма нового окна = сумма старого − arr[i−k] + arr[i]. Каждый элемент входит и выходит ровно один раз: всего 2n операций вместо n·k. Приём обобщается на переменную ширину окна и подсчёт вхождений.
Пошаговый разбор
- 01
Первое окно
Считаем сумму первых k элементов.
- 02
Выход
Вычитаем arr[i−k].
- 03
Вход
Прибавляем arr[i].
- 04
Сдвиг
Рамка переезжает, сумма уже готова.
- 05
Максимум
Лучшее окно запоминается.
Complexity и ограничения
Ширина фиксированная. Всего 2n обновлений, O(1) памяти.
Edge cases
- k = n
Одно окно — ответ сразу.
- Все отрицательные
Максимум — наименее плохое окно.
- k = 1
Вырождается в поиск максимума.
Где встречается в реальности
Тиковые графики
Скользящее среднее цены — то же окно по потоку котировок.
Лимиты запросов
Подсчёт событий за последние N секунд — окно по времени.
Сглаживание метрик
Rolling average в мониторинге.
Связанные алгоритмы
«Сумма окна без пересчёта: 2n операций вместо n·k»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.