Алгоритм скользящего окна¶

Алгоритм скользящего окна — это метод обработки последовательных данных (массивов, строк, списков), при котором на каждом шаге вычислений анализируется не весь набор данных, а только его непрерывный фрагмент фиксированного или переменного размера, называемый окном. Окно последовательно перемещается (скользит) по данным, что позволяет решать задачи, связанные с поиском подмассивов, подстрок или подпоследовательностей, за линейное время O(n) вместо квадратичного O(n²) при наивном переборе.

¶История и происхождение

Концепция скользящего окна возникла в контексте обработки сигналов и цифровой фильтрации в середине XX века. В компьютерных науках метод начал активно применяться с развитием алгоритмов обработки строк и массивов. Одним из ранних примеров является алгоритм Бойера — Мура для поиска подстроки (1977 год), где используется скользящее окно для сравнения образца с текстом. В современном программировании алгоритм стал стандартным инструментом для решения задач на собеседованиях, особенно в компаниях, практикующих технические интервью (например, Google, Amazon, Яндекс).

¶Основные принципы работы

Алгоритм скользящего окна основан на поддержании двух указателей (левый и правый), которые определяют границы окна. Окно может быть:

• Фиксированного размера — длина окна задана заранее и не меняется в процессе.
• Динамического (переменного) размера — длина окна изменяется в зависимости от условий задачи (например, пока не выполнено некоторое условие).

На каждом шаге алгоритм:

1. Добавляет новый элемент в окно (сдвигает правый указатель).
2. Выполняет вычисления для текущего окна (сумма, количество, проверка условия).
3. При необходимости сдвигает левый указатель, удаляя элемент из окна.
4. Повторяет шаги до конца данных.

¶Пример для фиксированного окна

Задача: найти максимальную сумму подмассива длины k в массиве чисел.

Наивное решение требует O(n*k) операций. Со скользящим окном:

• Вычисляем сумму первых k элементов.
• Затем для каждого следующего шага вычитаем уходящий элемент и добавляем новый.
• Сложность: O(n).

¶Пример для динамического окна

Задача: найти наименьшую подстроку, содержащую все символы заданного шаблона (например, задача «Minimum Window Substring» на LeetCode). Окно расширяется вправо, пока не содержит все нужные символы, затем сужается слева для минимизации длины.

¶Классификация и виды

¶По типу окна

• Фиксированное окно — используется, когда размер подмассива известен (например, «максимальная сумма подмассива длины k»).
• Динамическое окно — применяется, когда требуется найти подмассив, удовлетворяющий условию, без заранее заданной длины (например, «самая длинная подстрока без повторяющихся символов»).

¶По направлению движения

• Однонаправленное скольжение — окно движется только вперёд (наиболее распространённый случай).
• Двунаправленное скольжение — окно может расширяться и сжиматься с обеих сторон (используется реже, например, в алгоритмах сжатия данных).

¶По способу обновления

• Скользящее окно с накоплением — для каждого нового окна вычисляется значение на основе предыдущего (например, сумма, произведение).
• Скользящее окно с проверкой условия — окно изменяется, пока не выполнится или не нарушится некоторое условие (например, «сумма элементов не превышает S»).

¶Применение

¶Обработка массивов и строк

• Поиск максимальной/минимальной суммы подмассива фиксированной длины.
• Поиск самой длинной подстроки без повторяющихся символов.
• Поиск подстроки, содержащей все символы шаблона.
• Подсчёт количества подмассивов, удовлетворяющих условию (например, сумма ≤ K).
• Анализ временных рядов: скользящее среднее, скользящая медиана.

¶Сетевые технологии

• Управление перегрузкой в протоколе TCP (RFC 793, RFC 5681). Алгоритм скользящего окна используется для регулирования объёма данных, передаваемых без подтверждения приёма. Размер окна динамически изменяется в зависимости от состояния сети.
• Буферизация потокового видео (например, HLS, DASH) — окно определяет, какие фрагменты контента загружены и доступны для воспроизведения.

¶Базы данных

• Оконные функции в SQL (например, OVER (ORDER BY ... ROWS BETWEEN ...)). Реализуют скользящее окно для вычисления агрегатов (сумма, среднее, ранг) на наборе строк, упорядоченных по определённому столбцу.

¶Компьютерное зрение

• Скользящее окно применяется в детекторах объектов (например, в классическом методе Viola-Jones для распознавания лиц). Окно фиксированного размера перемещается по изображению, и на каждой позиции классификатор определяет, содержит ли окно искомый объект.

¶Обработка естественного языка

• N-граммы (последовательности из n слов) — частный случай скользящего окна для анализа текста.
• Построение контекстных векторов в моделях Word2Vec (CBOW и Skip-gram) использует окно для определения контекстных слов.

¶Сложность и ограничения

¶Временная сложность

• Для фиксированного окна: O(n), где n — длина последовательности.
• Для динамического окна: O(n) в среднем, так как каждый элемент добавляется и удаляется не более одного раза.
• В худшем случае (например, при полном переборе всех возможных окон) сложность может достигать O(n²), но это противоречит идее алгоритма.

¶Пространственная сложность

• O(1) для простых задач (сумма, длина).
• O(k) для задач, требующих хранения содержимого окна (например, хеш-таблица для подсчёта символов), где k — максимальный размер окна.

¶Ограничения

• Алгоритм эффективен только для задач, где свойство окна может быть вычислено инкрементально (на основе предыдущего состояния). Если каждое новое окно требует полного пересчёта, выигрыша в скорости нет.
• Не подходит для задач, где требуется анализировать все возможные подмассивы независимо (например, поиск всех пар элементов с заданной суммой — здесь лучше использовать хеш-таблицы).

¶Примеры реализации

¶Python: фиксированное окно (максимальная сумма подмассива длины k)

``python def max_sum_fixed_window(arr, k): n = len(arr) if n < k: return None window_sum = sum(arr[:k]) max_sum = window_sum for i in range(k, n): window_sum += arr[i] - arr[i - k] max_sum = max(max_sum, window_sum) return max_sum ``

¶Python: динамическое окно (самая длинная подстрока без повторяющихся символов)

``python def longest_unique_substring(s): char_set = set() left = 0 max_len = 0 for right in range(len(s)): while s[right] in char_set: char_set.remove(s[left]) left += 1 char_set.add(s[right]) max_len = max(max_len, right - left + 1) return max_len ``

¶Интересные факты

• Термин «скользящее окно» в контексте алгоритмов впервые был популяризирован в книге «Introduction to Algorithms» (Кормен, Лейзерсон, Ривест, Штайн) в разделе, посвящённом обработке строк.
• В протоколе TCP размер окна может достигать 65535 байт (классическое значение) или до 1 ГБ при использовании опции масштабирования окна (RFC 1323).
• Алгоритм скользящего окна используется в некоторых реализациях алгоритма сжатия LZ77 (Lempel-Ziv), где окно содержит ранее закодированные данные для поиска повторяющихся фрагментов.
• В задачах на собеседованиях скользящее окно — одна из самых частых тем, наряду с бинарным поиском и динамическим программированием.

¶Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ», 3-е издание, 2013.
• RFC 793 — Transmission Control Protocol, 1981.
• RFC 5681 — TCP Congestion Control, 2009.
• LeetCode — задачи «Sliding Window Maximum», «Minimum Window Substring», «Longest Substring Without Repeating Characters».
• GeeksforGeeks — статья «Sliding Window Technique», 2023.