Ctrl K
ВойтиНачать бесплатно
Урок

Скользящее окно

Интуиция: окно в поезде

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

На этом и держится скользящее окно. Окно — это непрерывный кусок массива или строки от индекса left до right. Мы двигаем его по данным и обновляем ответ за O(1) на каждом шаге, а не пересчитываем весь кусок заново.

Узнать задачу на окно можно по словам «подмассив», «подстрока», «подряд идущие» и «самый длинный / самый короткий / максимальная сумма».

Окно фиксированной длины

Допустим, нужна сумма каждых k подряд идущих элементов. В лоб пришлось бы для каждого начала складывать k чисел, это O(n·k).

С окном всё проще. Посчитай сумму первых k элементов, а дальше на каждом шаге:

  • прибавь вошедший справа элемент a[right];
  • вычти вышедший слева a[right - k].

Короче говоря, sum += a[right] - a[right - k]. Получается один проход и O(n). Размер окна не меняется, оно просто едет вправо, как рамка.

Окно переменной длины

Интереснее, когда длина окна заранее неизвестна и её нужно подобрать. Возьмём свой пример: найти длину самого длинного подмассива с суммой ≤ limit (числа неотрицательные).

Идея похожа на гусеницу:

  1. Голова (right) всегда ползёт вперёд и захватывает новый элемент.
  2. Если окно стало «плохим» (сумма > limit), хвост (left) подтягивается, пока окно снова не станет хорошим.
  3. Теперь окно корректно, и можно обновить ответ.

Возьмём [2, 1, 3, 2, 4, 1] и limit = 6.

Момент 1. right дошёл до индекса 2. Сумма 2+1+3 = 6, это ≤ 6, окно хорошее, длина 3.

left ↓ 20
11
right ↓ 32
23
44
15
Окно [0..2]: сумма 6 ≤ 6, длина 3 — пока лучший ответ

Момент 2. right шагает на индекс 3, сумма становится 8 > 6. Окно сломалось, поэтому сжимаем: убираем a[0] = 2, сумма 6, left = 1. Окно снова хорошее.

20
left ↓ 11
32
right ↓ 23
44
15
Добавили 2 → сумма 8, сдвинули left → сумма 6, окно [1..3] снова корректно

Заметь, что left никогда не идёт назад. Оба указателя двигаются только вправо.

Шаблон переменного окна

def longest_with_sum_at_most(a, limit):
    left = 0
    window_sum = 0
    best = 0
    for right in range(len(a)):
        window_sum += a[right]          # расширяем: берём a[right]
        while window_sum > limit:       # пока условие нарушено
            window_sum -= a[left]       # выкидываем элемент слева
            left += 1
        best = max(best, right - left + 1)  # окно корректно — обновляем ответ
    return best

Этот каркас подходит почти к любой задаче на переменное окно. Меняются только три вещи: что храним о состоянии окна, когда окно плохое и что обновляем в ответе.

То же самое на строке

На строке схема та же, меняется только состояние окна. Обычно это словарь-счётчик символов. Пусть условие звучит как «в окне не больше двух разных букв». Тогда:

  • при сдвиге right делаем count[s[right]] += 1;
  • окно плохое, если len(count) > 2;
  • при сдвиге left уменьшаем счётчик count[s[left]], а если он стал нулём, удаляем ключ.

Сначала словами сформулируй, что значит «окно плохое». Если это получилось, код почти пишется сам.

Почему это O(n), хотя внутри вложенный цикл

Вложенный while часто пугает: кажется, что тут O(n²). Но давай посчитаем ходы указателей:

  • right проходит массив один раз, это n шагов;
  • left тоже двигается только вперёд и в сумме сделает не больше n шагов.

Каждый элемент один раз входит в окно (через right) и не больше одного раза выходит (через left). Всего операций не больше 2n, значит O(n) по времени. Память O(1) для суммы или O(размер алфавита) для счётчика.

Подход Время Память
Перебор всех подмассивов O(n²) или O(n³) O(1)
Скользящее окно O(n) O(1) / O(σ)

Как это звучит на собесе

«Перебор всех подмассивов даёт O(n²). Заметим, что если окно стало плохим, расширять его дальше бессмысленно, нужно сжимать слева. Поэтому используем два указателя: right расширяет окно, left сжимает, пока условие нарушено. Каждый элемент входит и выходит из окна максимум по разу, итого O(n)».

Хороший сигнал для интервьюера — когда ты сам проговариваешь, почему окно монотонно: расширение только ухудшает условие, а сжатие только улучшает.

Частые ошибки

  • Отрицательные числа. Если они есть, «сумма > limit → сжимай» перестаёт работать: сжатие может сумму увеличить. Окно годится, когда условие монотонно. Иначе обычно помогают префиксные суммы, о них в следующем уроке.
  • if вместо while. Одного сдвига left может не хватить, сжимай до тех пор, пока окно не станет корректным.
  • Ответ обновлён не там. Для «самого длинного» обновляй после while, когда окно уже хорошее. Для «самого короткого» обычно обновляют внутри while, пока окно ещё удовлетворяет условию.
  • Длина окна. Она равна right - left + 1, про +1 легко забыть.
  • Мусор в счётчике. Если не удалять ключи с нулём, len(count) будет врать.

Если ты понял гусеницу «голова вперёд, хвост подтягивается, пока плохо», то главное ты уже знаешь. Дальше в практике этот же каркас применяется к разным условиям.