Модуль 21 ⏱ ~15 мин чтения 📐 1 Mermaid диаграмм

1. Теория. Скользящее окно

Sliding Window

«Вместо того чтобы раз за разом пересчитывать всё с нуля, помните прошлое и обновляйте только то, что изменилось на границе».
— Брайан Керниган

Тема: Фундаментальные алгоритмические паттерны, инкрементальный пересчет состояния, $O(N)$ на подмассивах
Ссылки: Теория: Два указателя, Фиксированное и динамическое окно, Maximum Average Subarray I, Longest Substring

1. Введение и физическая интуиция

Представьте движущийся поезд с панорамными окнами фиксированного размера. Пассажир смотрит в окно: по мере движения поезда в правый край стекла вплывают новые пейзажи (деревья, дома, горы), а из левого края стекла точно такие же объекты навсегда исчезают.

Чтобы узнать суммарную яркость или количество деревьев в поле зрения, пассажиру не нужно каждый метр заново пересчитывать все деревья в окне! Достаточно простой формулы:
$$ \text{Текущее состояние} = \text{Предыдущее состояние} + \text{Новый вошедший объект} - \text{Старый вышедший объект} $$

В этом заключается фундаментальная магия скользящего окна (Sliding Window):

  • Мы сворачиваем полный квадратичный перебор всех непрерывных подмассивов ($O(N^2)$ или $O(N \times K)$) в строго один линейный проход $O(N)$.
  • На каждом шаге сдвига границы мы тратим ровно $O(1)$ операций на обновление внутреннего аккумулятора (суммы, частотного словаря, счетчика).
flowchart TD
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc

    Start["Окно [left .. right]<br>Аккумулятор состояния State"]:::entry --> Expand["1. Расширение: right++<br>State += item[right]"]:::process
    Expand --> Check{"Инвариант окна<br>сохраняется?"}:::warning
    Check -->|"Да (Окно валидно)"| Update["Обновить глобальный ответ<br>(max/min длина, сумма)"]:::success
    Check -->|"Нет (Нарушение)"| Shrink["2. Сжатие: State -= item[left]<br>left++"]:::process
    Shrink --> Check
    Update --> Next{"right < n-1?"}:::warning
    Next -->|"Да"| Expand
    Next -->|"Нет"| Done["Финал: вернуть лучший ответ"]:::success

2. Отличие от классических двух указателей

В кластере Два указателя мы оперировали индексами, анализируя только сами крайние элементы: arr[left] и arr[right].

Скользящее окно — это два указателя с памятью состояния:

  1. Между left и right всегда находится непрерывный диапазон данных (contiguous subarray / substring).
  2. Алгоритм непрерывно поддерживает агрегированное состояние этого диапазона (sum, freq[26]int, count).
  3. При сдвиге правого указателя состояние инкрементируется за $O(1)$.
  4. При сдвиге левого указателя состояние декрементируется за $O(1)$.

3. Критерии применимости скользящего окна

Паттерн гарантированно применим, если выполняются три условия:

  1. Непрерывность (Contiguous Subsegment): задача требует найти оптимальный подмассив, подстроку или срез. Элементы нельзя пропускать или переставлять.
  2. Инкрементальность пересчета ($O(1)$ Update): добавление одного элемента в правый край и удаление одного элемента из левого края пересчитывает метрику без полного сканирования всего окна.
  3. Монотонность (для динамического окна): расширение окна вправо либо только увеличивает метрику, либо только приближает нас к нарушению условия. Например, сумма неотрицательных чисел монотонно растет при расширении.

4. Классификация окон: фиксированные и динамические

Характеристика Фиксированное окно (Fixed-size) Динамическое окно (Variable-size)
Длина окна ($K$) Константа, задана явно в условии Переменная величина ($right - left + 1$)
Управление left Жесткая связь: $left = right - K + 1$ Сдвигается в цикле while, пока нарушено условие
Цель оптимизации Найти экстремум метрики в окне длины $K$ Найти минимальную или максимальную длину окна
Сложность по времени Строго $N$ итераций ($O(N)$) $2N$ итераций в худшем случае ($O(N)$ амортизировано)
Примеры задач Maximum Average Subarray, Find All Anagrams Longest Substring Without Repeating, Minimum Window Substring

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

5. Mechanical Sympathy: структуры данных и кэш процессора

Эффективность скользящего окна в реальном рантайме Go на $90\%$ определяется выбором структуры для хранения состояния:

1. Статический массив на стеке ([26]int / [128]int) — Абсолютный фаворит:

Если алфавит задачи ограничен (ASCII, латиница a–z), состояние окна хранится в массиве фиксированного размера:

Go 
var window [128]int // 128 * 8 = 1024 байта на стеке
window[s[right]]++  // 1 инструкция CPU LEA/MOV
window[s[left]]--   // 1 инструкция CPU
  • 0 аллокаций в куче (0 B/op).
  • Помещается в L1d-кэш процессора.
  • Сравнение окон window == target компилируется в векторный memequal.

2. Хэш-таблица (map[byte]int) — Только при необходимости:

Если набор ключей заранее неизвестен или слишком разрежен:

  • Требует вызова runtime.mapassign и runtime.mapaccess.
  • Каждый доступ к ключу — это вычисление хэша и поиск по цепочке бакетов (~$30\text{--}50$ тактов).
  • Операция delete(m, key) не освобождает память бакетов немедленно, создавая фрагментацию.
  • Обязательно предвыделяйте вместимость: make(map[byte]int, 128).

6. Вопросы для собеседования

7. Чек-лист готовности к кластеру

  • [x] Понимаю разницу между фиксированным и динамическим окном.
  • [x] Помню, что при наличии отрицательных чисел скользящее окно на сумму неприменимо.
  • [x] Использую плоские массивы [26]int или [128]int вместо map везде, где алфавит ограничен.
  • [x] Умею доказать интервьюеру линейность $O(N)$ через амортизацию сдвигов.

Приступаем к детальному изучению анатомии фиксированных и динамических окон: 2. Фиксированное и динамическое окно.