Алгоритмы на массивах · модуль 9 · скользящее окно

Глава 9.2

Формулировки задач
и вопросы до решения

В этой главе разобрано, как звучит задача на окно фиксированной длины и что уточнить до кода. Сначала — части условия и слова, по которым узнаётся окно, восемь формулировок и случаи, когда окно не подходит. Затем — разговор с интервьюером о задаче КТП «лучший отрезок длины k», контракт функции и тестовые примеры, которые записывают до решения. В конце — тренажёр выбора техники.

Категория: Работа с условием
Уровень: Начальный
Опирается на: Глава 9.1; главы 8.2 и 8.3: признаки в условии и уточняющие вопросы
Зачем это знать: Узнавать окно по условию и уточнять задачу до кода

§1Из чего состоит условие

Условие задачи на окно состоит из тех же частей, что в главе 8.2: легенда, входные данные, результат, ограничения. У задачи на окно фиксированной длины во входных данных есть ещё одна обязательная часть — длина окна. Обычно это отдельный параметр k, иногда она названа в легенде: «за любые 3 часа подряд», «за неделю».

Как звучитСайт считает посетителей каждый час. Найдите, за какие k часов подряд посетителей было больше всего, и верните начало этого промежутка и число посетителей.

→

Что это значитВход: список чисел и число k. Результат: индекс начала отрезка длины k с наибольшей суммой и сама сумма.

Легендасайт, посетители, часы

→

Для решения не нужнаТа же задача про выручку магазина за любые 7 дней подряд решается тем же кодом.

Признаки«k часов», «подряд», «больше всего»

→

Что подсказываютДлина участка задана числом, участок непрерывный, нужен лучший из всех таких участков — окно фиксированной длины.

§2Восемь формулировок

Ниже восемь условий без подсказки, какую технику применить. Семь из них — пересказы задач LeetCode, ссылка в шапке карточки; условия сверены с сайтом. Восьмая — вторая задача КТП занятия 9. Кнопка под карточками подсвечивает слова, по которым узнаётся окно фиксированной длины.

Лучшее среднееLeetCode 643

Дан массив чисел и число k. Найдите непрерывный подмассив длины k с наибольшим средним и верните это среднее.

ГласныеLeetCode 1456

Дана строка и число k. Верните наибольшее число гласных в подстроке длины k.

Среднее не ниже порогаLeetCode 1343

Дан массив и числа k и threshold. Посчитайте, сколько подмассивов размера k имеют среднее не меньше threshold.

Перекраска блоковLeetCode 2379

Строка из букв W и B — белые и чёрные блоки. За одну операцию белый блок можно перекрасить в чёрный. Найдите наименьшее число операций, чтобы получилось k чёрных блоков подряд.

Сердитый продавецLeetCode 1052

Известно, сколько покупателей приходит в каждую минуту и в какие минуты продавец сердит. Один раз за день он может не сердиться minutes минут подряд. Верните наибольшее число довольных покупателей.

Среднее вокруг элементаLeetCode 2090

Для каждого индекса i найдите среднее элементов с i − k по i + k. Если слева или справа меньше k элементов, запишите −1.

Три разных буквыLeetCode 1876

Посчитайте, сколько подстрок длины три состоят из трёх разных букв. Одинаковые подстроки в разных местах считаются отдельно.

События в окнеКТП, занятие 9

Даны моменты времени событий в секундах. Найдите наибольшее число событий, которые попадают в любой промежуток длиной w секунд.

§3Признаки в условии

Подсвеченные слова повторяются от задачи к задаче. Технику выбирают по сочетанию признаков: участок идёт подряд, его длина задана числом и для каждого такого участка считается одна и та же величина.

Слова в условии	Что они сообщают	Вывод
«длины k», «размера k», «за k минут», «за неделю»	Длина участка задана числом и одинакова для всех участков	окно фиксированной длины
«подряд», «непрерывный», «подмассив», «подстрока»	Участок — элементы, стоящие рядом, без пропусков	окно: элементы выбираются только подряд
«наибольший», «наименьший», «лучший»	Из всех окон нужно одно, лучшее по величине	пройти все окна, хранить лучшее
«сколько подмассивов», «сколько подстрок»	Нужно число окон, для которых выполнено условие	пройти все окна, вести счётчик
«для каждого», «для каждого дня»	Ответ — значение для каждого окна, список длины `n − k + 1` или `n`	пройти все окна, записывать ответ
«любой промежуток w секунд»	Длина окна задана в секундах; число элементов в окне меняется	окно по времени, глава 9.5

§4Когда окно фиксированной длины не подходит

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

УсловиеНайдите самый короткий подмассив с суммой не меньше S. Длина не задана.

РешениеДлину окна определяет условие «сумма не меньше S», числа k в задаче нет. Это окно переменной длины: правая граница расширяет окно, левая сжимает. LeetCode 209, занятие 10.

УсловиеВыберите любые k чисел с наибольшей суммой, не обязательно подряд.

РешениеУчасток не непрерывный, и окно здесь ни при чём. Достаточно взять k наибольших чисел: например, отсортировать список, это O(n log n). Быстрее — кучей, это занятие 33 о heap и priority queue.

УсловиеДля каждого окна длины k найдите максимум.

РешениеОкно фиксированной длины подходит, но максимум не исправить по ушедшему элементу: если ушёл сам максимум, новый неизвестен без просмотра окна. Нужна дополнительная структура — дек. LeetCode 239, занятие 25.

На полях: отрицательные числа окну не мешают

В главе 8.2 отрицательные числа ломали задачу «подотрезок с суммой ровно S»: сумма при сдвиге границы может и вырасти, и уменьшиться. Окну фиксированной длины это не важно. Оно проходит все n − k + 1 окон подряд и ничего не пропускает, поэтому знак чисел на ход алгоритма не влияет. В LeetCode 643 числа как раз бывают отрицательными: от −10⁴ до 10⁴.

§5Разговор с интервьюером о лучшем отрезке

Первая задача КТП занятия 9 — найти лучший отрезок длины k. Слева — условие в том виде, в каком его произнёс интервьюер. Справа — вопросы. После каждого вопроса появляются ответ интервьюера и то, что он меняет в решении, а слева — новое уточнение. Порядок вопросов любой.

Лучший отрезок длины k

условие от интервьюера

«Дан список чисел — посещения сайта по часам — и число k. Найдите k часов подряд, за которые посетителей было больше всего».

уточнено

Два ответа меняют код сильнее остальных. Ответ про отрицательные числа меняет начальное значение лучшей суммы. Ответ про k задаёт поведение на неверном входе: в КТП контроль занятия 9 прямо требует «тесты k=0/1/n и неверного k».

§6Контракт функции

После разговора условие записывается как контракт: что функция принимает, что возвращает и что делает на неверном входе. В таблице для каждого ответа указано, какую часть решения он определяет.

Ответ интервьюера	Куда попадает	Что это значит для решения
Вернуть начало и сумму	Формат результата	Кортеж `(start, total)`, хранить индекс лучшего окна
При равных суммах — самое левое окно	Сравнение	Обновлять лучшее только при строго большей сумме
Числа бывают отрицательными	Начальное значение	Лучшая сумма начинается с суммы первого окна
k от 1 до n, иначе `ValueError`	Проверка входа и тесты	Проверка в первой строке, тесты на `k = 0`, `k < 0`, `k > n`, пустой список
n до 10⁶, вход не менять	Выбор способа	Сдвиг окна, время O(n), память O(1); тест, что список после вызова тот же

solution.pyконтракт после уточнений

def best_window(nums, k):
    """Скользящее окно фиксированной длины. Задача 1 занятия 9.

    nums — список целых чисел, числа могут быть отрицательными.
    k — длина окна, 1 <= k <= len(nums); иначе ValueError.
    Возвращает (start, total): начало окна длины k с наибольшей суммой
    и эту сумму. При равных суммах — самое левое окно. Список не меняется.
    Время O(n), память O(1).
    """

§7Вопросы к задаче о событиях

У второй задачи КТП вопросы другие: окно в ней задано длиной по времени, и в одном окне может оказаться разное число событий. Разговор строится так же — каждый вопрос заканчивается изменением в решении. Сама задача разобрана в главе 9.5.

Вопрос	Типичный ответ	Что меняет
Моменты событий отсортированы?	Да, по возрастанию	События окна идут подряд, границы окна двигаются только вправо. Если не отсортированы — сначала сортировка, O(n log n)
Окно длиной w — это [t, t + w) или [t, t + w]?	Полуинтервал [t, t + w)	Событие в момент `t + w` в окно не входит; нужен пример с событием ровно на границе
Бывают ли события в один и тот же момент?	Да	Одинаковые моменты считаются разными событиями; нужен пример с повтором
Что вернуть?	Наибольшее число событий в одном окне	Функция возвращает число; пустой список даёт 0

На полях: окно по времени и окно по элементам

В задаче о посещениях окно — это k элементов, и при сдвиге уходит ровно один элемент. В окне по времени длиной w секунд может быть и ноль событий, и сто. При сдвиге может уйти несколько событий сразу, поэтому левую границу двигают циклом. Длина окна по времени постоянна, а число элементов в нём — нет.

§8Тестовые примеры до кода

Как и в главе 8.3, после вопросов записывают входы с ответами. Каждый пример проверяет свой класс входа: обычный случай, ответы на уточнения и три значения k из контроля КТП. Ответы получены запуском эталонного решения на Python 3.12.

nums	k	Ответ	Что проверяет
`[12, 15, 9, 20, 18, 7, 25]`	3	`(4, 50)`	обычный случай: лучшее окно — последнее
`[5, 1, 5, 1]`	2	`(0, 6)`	все окна дают 6, возвращается самое левое
`[-5, -2, -8, -1]`	2	`(0, -7)`	все суммы отрицательные
`[3, -2, 7]`	1	`(2, 7)`	`k = 1`: окно — один элемент, ответ — наибольший элемент
`[4, 1, 2]`	3	`(0, 7)`	`k = n`: одно окно — весь список
`[1, 2]`	0	`ValueError`	`k = 0`: неверный вход
`[1, 2]`	3	`ValueError`	`k > n`: окна такой длины нет
`[]`	1	`ValueError`	пустой список

Пример с отрицательными числами ловит частую ошибку — начальное значение best = 0. На нём такая версия вернёт сумму 0, хотя ни одно окно её не даёт. Этот и остальные примеры войдут в тесты стартового набора.

§9Тренажёр: выберите технику

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

Условие 1Датчик присылает показание раз в минуту. Найдите наибольшую сумму показаний за любые 10 минут подряд.

10 наибольших показаний могут стоять в разных местах, а нужны 10 минут подряд. Сортировка теряет порядок.
Верно. Участок подряд, длина задана числом, сумма исправляется по ушедшему и пришедшему показанию. Время O(n).
Ответ будет верным, но каждое окно пересчитывается за 10 сложений: O(n·k) против O(n) у сдвига.

Условие 2Цены отсортированы по возрастанию. Найдите две цены с суммой ровно 1000 и верните их индексы.

Окно длины 2 проверяет только соседние цены. Пара с суммой 1000 может стоять далеко друг от друга.
Чтение и запись нужны, когда список меняется на месте. Здесь нужна пара элементов.
Верно. Это задача 1 модуля 8: отсортированный вход, пара с заданной суммой.

Условие 3Для каждого дня, начиная с седьмого, найдите среднюю температуру за последние 7 дней.

Верно. Это скользящее среднее, как rolling(7) из главы 9.1: сумма окна исправляется при сдвиге, среднее — сумма, делённая на 7.
Ответ верный, но каждое окно стоит 7 сложений вместо двух операций. При длинном окне разница становится большой.
Указатели навстречу сравнивают элементы с разных концов. Здесь нужны участки подряд.

Условие 4Выберите любые три числа из списка с наибольшей суммой. Стоять подряд им не обязательно.

Окно рассматривает только три числа подряд. Три наибольших числа могут быть в разных местах списка.
Верно. Порядок не важен, поэтому окно не нужно. Три наибольших можно найти одним проходом или сортировкой.
Ответ будет верным, но троек около n³/6 — это O(n³).

Условие 5Найдите самый короткий отрезок с суммой не меньше 100. Числа положительные.

Это верно, но для каждого k нужен свой проход, всего O(n²). Длина в условии не задана.
Верно. Длину задаёт условие «сумма не меньше 100». Окно расширяется вправо, пока сумма мала, и сжимается слева, пока она достаточна. Один проход, O(n).
Сортировка теряет порядок, а отрезок должен идти подряд.

Условие 6Строка из букв W и B. Сколько белых блоков нужно перекрасить, чтобы где-то стояли 4 чёрных подряд?

Перекрашивать нужно только внутри одного участка из 4 блоков, остальные белые не важны.
Самая длинная серия может быть короче 4, и вокруг неё может быть больше белых, чем в другом месте.
Верно. Это LeetCode 2379: в каждом окне длины 4 считают белые блоки, ответ — наименьшее их число. Счётчик белых исправляется при сдвиге.

Модуль 9 · Скользящее окно · ОП.04 · 3 курс Автор: Макаров Максим Николаевич