pattern heroPT–23LeetCode Extension

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

Смотрим на отрезок данных как на окно, которое едет вперёд: с одного края элемент входит, с другого выходит. Окно не собирают заново на каждом шаге, поэтому данные проходятся один раз, а не перебираются все отрезки.

Вариант
P03 Скользящее окноПеременный размер · 1×

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

0a1b2a3c4d5e6c7f
окноследующий символлучшее окно

Начинаем с пустого окна

window = {}left = –best = –right = –
01/48
сначала · назад · пуск · шаг
Скорость
1function longestWithoutRepeats(s):
2 window = empty set
3 left = 0
4 best = 0
5 for right from 0 to len(s) - 1:
6 while s[right] in window:
7 remove s[left] from window
8 left = left + 1
9 add s[right] to window
10 best = max(best, right - left + 1)
11 return best

← → шаг · пробел — пауза

Как узнать

непрерывный подмассив или подстрока, самый длинный или самый короткий с условием.

Как решать такие задачи

  1. Сформулируй правило хорошего окна: без повторов, сумма не больше k, не больше k разных букв.
  2. Реши, что хранить об окне, чтобы правило проверялось быстро: множество, словарь счётчиков, текущую сумму.
  3. Расширяй окно справа. Пока оно нарушает правило, сужай его слева.
  4. Обновляй ответ, пока окно хорошее: для самого длинного после сужения, для самого короткого во время сужения.

Вариант: Фиксированный размер

То же, но размер окна не меняется: на каждом шаге один элемент входит и один выходит. Ответ для окна не считаем заново, а поправляем от предыдущего.

  1. Убедись, что длина окна фиксирована: k чисел подряд, подстрока длиной с образец.
  2. Реши, что хранить об окне, чтобы один вошедший или ушедший элемент обновлял это за O(1): текущую сумму, словарь счётчиков букв.
  3. Собери первое окно из первых k элементов и запиши для него ответ.
  4. Сдвигай: добавь элемент на right, убери элемент на right - k и обнови ответ. Так же считаются средние и окна-анаграммы со счётчиками букв.

Где встречается

  • TCP. Отправитель шлёт несколько пакетов, не дожидаясь ответа, но не больше, чем позволяет окно. Когда приходит подтверждение, окно сдвигается вперёд и можно слать следующие.
  • gzip и zip. Их сжатие, DEFLATE, ищет повторы в последних 32 КБ текста. Окно едет вместе с текстом, а найденный повтор заменяется короткой ссылкой назад.
  • Ограничение запросов. Правило «не больше 100 запросов за последнюю минуту» — это окно в одну минуту, которое едет вместе со временем. Так считает лимиты Cloudflare.