Метод скользящего окна

Метод скользящего окна – это приём линейного прохода по последовательности с поддержанием «окна» фиксированной или переменной длины, внутри которого поддерживаются агрегаты (сумма, максимум/минимум, частоты, количество уникальных и т. п.). Цель – вычислять характеристики для всех (или многих) подряд идущих подотрезков за амортизированное O(1) на шаг, приводя общую сложность к O(n) вместо наивного O(n·k).

Ключевые эффекты:

• уменьшение асимптотики за счёт инкрементального обновления агрегатов (вычесть ушедший элемент, прибавить пришедший);
• поддержка инвариантов для «быстрых» запросов (монотонные очереди/деки для экстремумов);
• естественная работа с потоками и онлайн-задачами.

Связь с ЕГЭ: задания на массивы, строки, подсчёт частот, поиск подотрезков с ограничениями, «скользящие» суммы/максимумы, двуточечные техники (two pointers) – всё это регулярно встречается в тренировочных наборах и демонстрационных вариантах.

Формальная модель и инварианты

Пусть дана последовательность A = (a0, a1, …, a_{n-1}). Окно длины k над индексом r – это подотрезок

W(r) = A[r-k+1 .. r],   r ≥ k-1

Если длина переменная, задаётся условием P(W) (например, сумма ≤ S или максимум−минимум ≤ D). Тогда окно описывается парой указателей (L, R) (левая и правая граница), где 0 ≤ L ≤ R < n, и инвариантом допустимости:

I(W):  P( A[L..R] ) = True,   а расширение до A[L..R+1] нарушает P (при необходимости).

1. Инкрементальные агрегаты
   

   Для фиксированной длины k и аддитивной метрики:

   S(r) = Σ_{i=r-k+1..r} a_i

   S(r+1) = S(r) − a_{r−k+1} + a_{r+1}

   Аналогично для средних, дисперсий (с поправками), частотных таблиц и т. п.

2. Инварианты корректности
   

   • I1 (границы): 0 ≤ L ≤ R < n.

   • I2 (допустимость): окно удовлетворяет ограничению P.

   • I3 (монотонность продвижения): L и/или R двигаются только вперёд, что обеспечивает линейную суммарную работу.

   • I4 (чистота структуры): вспомогательные структуры (дек/мультисет/частотный массив) содержат ровно элементы окна.

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

1. Фиксированное окно (fixed window)
   

   Дано k. Для всех r = k−1..n−1 требуется значение агрегата на A[r−k+1..r].

   Базовый паттерн:

   S := Σ_{i=0..k-1} a_i

   ответ для r = k−1 ← S

   для r = k .. n−1:

       S := S − a_{r−k} + a_{r}

       ответ для r ← S

   Сложность: O(n), память O(1).

2. Переменное окно с двигающейся левой границей (two pointers)
   

   Требуется максимальная длина подотрезка, удовлетворяющего P (например, сумма ≤ S).

   Паттерн:

   L := 0

   для R от 0 до n−1:

       включить a_R в агрегат

       пока P(A[L..R]) = False:

           исключить a_L из агрегата

           L := L + 1

       ответ/обновление по A[L..R]

   Сложность: каждый индекс входит/выходит не более 1 раза ⇒ O(n).

3. Монотонные деки для экстремумов
   

   Для «скользящего максимума/минимума» поддерживается дек индексов в монотонном порядке значений:

   • при добавлении r удаляем с хвоста индексы с меньшим (для максимума – нестрого меньшим) значением;

   • с головы выбрасываем индекс, если он вышел за окно.

   Ответ – элемент по индексу на голове дека.

   Сложность: каждый индекс добавлен/удалён ≤ 1 раза ⇒ O(n).

4. Частоты и количество уникальных 
   

   Поддерживаем cnt[x] и число уникальных uniq:

   • при добавлении x: cnt[x]++, если стало 1 – uniq++;

   • при удалении x: cnt[x]--, если стало 0 – uniq--.

   Сложность: O(1) амортизированно на обновление (при ограниченном алфавите или хеш-таблице).

Типовые задачи и шаблоны (массивы и строки)

1. Сумма/среднее/дисперсия на окне
   

   • Сумма: формула выше.

   • Среднее: μ(r) = S(r)/k.

   • СКО: поддерживать Σ a_i и Σ a_i^2:

   Var = (Σ a_i^2)/k − ( (Σ a_i)/k )^2

2. Максимум/минимум в окне
   

   Использовать монотонный дек:

   Пусть D – дек индексов убывающих значений a[i]

   для каждого r:

       пока D не пуст и a[D.back] ≤ a[r]: D.pop_back()

       D.push_back(r)

       если D.front < r−k+1: D.pop_front()

       если r ≥ k−1: ответ ← a[D.front]

3. Длина наибольшего подотрезка с ограничениями
   

   • сумма ≤ S (неотрицательные a_i) – two pointers;

   • max−min ≤ D – два дека (для max и min), см. инвариант «окно допустимо, пока разница ≤ D».

4. Подстроки и окна по символам
   

   • фиксированное k: скользящие хэши (Рабин–Карп) для поиска совпадений;

   • переменное: «наибольшая подстрока без повторов» – частоты и сдвиг L при cnt[s[R]] > 1.

Сложность и память

• Время: при корректном инкрементальном обновлении – O(n).
• Память: O(1) для простых агрегатов; O(алфавит) или O(k) для частот/деков.
• Амортизация: каждая операция вставки/удаления элемента из структуры – не более 1 раза.

Инженерные правила (чек-лист)

G1  Двигайте L и R только вперёд; не откатывайте указатели.

G2  Все изменения агрегатов – парные: «вышло из окна» ⇒ «удали», «вошло» ⇒ «добавь».

G3  Для экстремумов применяйте монотонные деки; не храните в них значения, храните индексы.

G4  В задачах с ограничением sum≤S используйте two pointers только при неотрицательных a_i.

G5  Для «max−min≤D» держите два дека (max и min); инвариант: a[max.front]−a[min.front] ≤ D.

G6  В строках используйте частотный массив/словарь; L сдвигайте до снятия нарушения.

G7  Все сравнения делайте на индексах, прежде чем выдавать ответ – «очистите голову» дека от устаревших индексов.

G8  Для чисел большой динамики избегайте переполнения сумм: используйте 64-битные типы, нормировки или префиксные суммы по модулю.

G9  Пограничные случаи: k=1, k>n, пустая строка, массив из одинаковых элементов.

G10 Проверяйте инварианты в отладочном режиме (ассерты на допустимость окна). 

Мини-шпаргалка 

Скользящая сумма (фикс. k):

S0 = Σ_{i=0..k-1} a_i

S_{r+1} = S_r − a_{r−k+1} + a_{r+1} 

Два указателя (sum≤S, a_i≥0):

L=0; sum=0

для R=0..n−1:

    sum += a[R]

    пока sum > S:

        sum -= a[L]; L++

    ответ по [L..R] 

Скользящий максимум через дек:

для r=0..n−1:

    пока D не пуст и a[D.back] ≤ a[r]: D.pop_back()

    D.push_back(r)

    если D.front < r−k+1: D.pop_front()

    если r ≥ k−1: max = a[D.front] 

Типичные ошибки и анти-паттерны

1. Сдвиг L без удаления a[L] из агрегата ⇒ некорректные результаты.
2. Хранение в деке значений вместо индексов ⇒ невозможно удалять ушедшие элементы.
3. Применение two pointers при отрицательных a_i в условии sum≤S ⇒ потеря корректности.
4. Двойная очистка головы дека ⇒ пропуск нужного индекса.
5. Отсутствие обработки краёв (k>n, пустые последовательности).

Расширения метода

• Скользящее окно в 2D (матрицы): свёртки по строкам → по столбцам; поддержка деков по каждой строке.
• Потоки (streaming): кольцевые буферы, экспоненциально взвешенные метрики.
• Онлайн-хэширование: rolling hash для строковых окон, «удаление» и «добавление» символов в хэш.
• Комбинация с двоичным поиском по ответу: проверка выполнимости ограничения с окном → оптимизация параметра.

Связь с ЕГЭ по информатике

• Алгоритмизация: линейные проходы, корректная работа с индексами.
• Структуры данных: очереди/деки, частотные массивы, хеш-таблицы.
• Строки: подстроки, частоты символов, подзадачи на уникальность/повторы.
• Массивы/числовые ряды: суммы, экстремумы, ограничения на диапазон.
• Сложность: доказательство O(n), работа с амортизацией.

Пять упражнений 

Упражнение 1. Скользящая сумма и среднее (фиксированное окно)

Дан массив A длины n и целое k (1 ≤ k ≤ n).
a) Для всех окон длины k вычислите сумму и среднее.
b) Докажите, что алгоритм со скользящей суммой работает за O(n).
c) Оцените числовую устойчивость при больших A[i] и предложите способ избежать переполнения.

Подсказка: используйте 64-битные целые; при вещественных – технику «Kahan sum» (по желанию).

Упражнение 2. Скользящий максимум через монотонный дек

Дано A и k.
a) Реализуйте поиск максимума на каждом окне длины k.
b) Докажите амортизированную O(1) стоимость операции за счёт единственного добавления/удаления каждого индекса.
c) Модифицируйте решение для скользящего минимума.

Упражнение 3. Максимальная длина подотрезка с суммой ≤ S

Дан массив неотрицательных чисел A и целое S.
a) Найдите максимальную длину подотрезка с суммой ≤ S методом двух указателей.
b) Объясните, почему корректность нарушается при наличии отрицательных значений.
c) Предложите альтернативный подход для массива с отрицательными элементами (например, префиксные суммы + двоичный поиск или структура поиска минимума).

Упражнение 4. Подстрока без повторяющихся символов

Дана строка s.
a) Найдите длину максимальной подстроки без повторений, используя частоты и сдвиг левой границы.
b) Покажите инвариант: каждый символ встречается в окне не более одного раза.
c) Оцените память для Unicode-алфавита и предложите реализацию на хеш-карте.

Упражнение 5. Ограничение на диапазон: max−min ≤ D

Дан массив A и число D ≥ 0.
a) Найдите максимальную длину подотрезка, где max(A[L..R]) − min(A[L..R]) ≤ D.
b) Реализуйте два монотонных дека: один для максимумов, другой для минимумов.
c) Докажите, что суммарная сложность – O(n), и приведите корректное условие сдвига L.

Развёрнутая проверка корректности (доказательные идеи)

• Лемма об амортизации: в любом из паттернов (монотонный дек, частоты, два указателя) индексы входят и покидают структуру по одному разу ⇒ суммарное число операций O(n).
• Инвариант допустимости окна: при нарушении условия P мы монотонно двигаем L, пока P не восстановится; так как L растёт, цикл «пока» суммарно выполняется не более n раз.
• Чистота структуры: любые вспомогательные данные соответствуют точному множеству индексов [L..R]; при каждом шаге убыточные (вышедшие/доминируемые) элементы удаляются.

Практические рекомендации и гигиена кода

• Пишите обёртки: push_right(x), pop_left(), shrink_until_ok().
• Введите диагностику: проверки головы/хвоста дека, синхронизация частот и длины окна.
• Для задач с большими k используйте deque стандартной библиотеки; для частот – упрощённые фиксированные массивы, когда алфавит ограничен.
• Тестируйте на наборах: пустые массивы, все элементы равны, строго возрастающие/убывающие, k=1, k=n.

Заключение

Метод скользящего окна – фундаментальный инструмент линейных алгоритмов, сочетающий строгие инварианты, амортизированную константную работу и компактную память. На практике он превращает «квадратичные» задачи на подотрезки и подстроки в линейные решения, а его комбинирование с монотонными деками, частотами и скользящими хэшами покрывает широкий класс экзаменационных и прикладных задач.

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