Где применяется
1. Задача
Дашборд мониторинга показывает среднее время ответа на запрос по последним 10 замерам. С каждым новым замером среднее нужно обновить. Приходит новое число, самое старое выпадает, и нужно свежее среднее.
Простой способ при каждом новом замере заново складывает все 10 чисел. Для десяти это пустяк. Теперь возьми окно из 10 000 замеров и историю из миллиона замеров. Это миллион раз по десять тысяч сложений, и почти все они повторяют работу, сделанную на предыдущем замере.
Почти все числа нового окна были и в старом. Их сумма уже посчитана. Если считать её с нуля, ты выбрасываешь ответ, который у тебя уже был.
2. Простыми словами
Тебе нужна величина (например, среднее) по нескольким последним показаниям, и она обновляется с каждым новым показанием. Если каждый раз складывать всё заново, работа пропадает зря: почти все числа остались теми же.
Возьми показания 4, 2, 1, 7 и окно из двух чисел. Сумма первого окна 4 + 2 = 6. Окно сдвигается на шаг: 1 входит, 4 выходит. Новая сумма 6 + 1 - 4 = 3, и складывать заново ничего не нужно. На каждом шаге работы ровно две: прибавить вошедшее число и вычесть вышедшее.
3. Идея
Храни сумму текущего окна. Когда окно сдвигается на шаг, ровно один элемент входит справа и ровно один уходит слева. Поэтому сумму обновляют двумя действиями: прибавь новый элемент, вычти ушедший.
Уходит всегда элемент, который стоит на k позиций раньше входящего. Если ширина окна k, а входящий элемент стоит на позиции i, то уходящий стоит на позиции i - k. Все элементы между ними остаются в окне, и они уже учтены в сумме.
Проследим на [4, 2, 1, 7, 8] с окном из 2 чисел.
- Первое окно
[4, 2], сумма 6. - Сдвиг: прибавляем 1, вычитаем 4, сумма 3. Это окно
[2, 1]. - Сдвиг: прибавляем 7, вычитаем 2, сумма 8. Это окно
[1, 7]. - Сдвиг: прибавляем 8, вычитаем 1, сумма 15. Это окно
[7, 8].
Самая большая сумма окна равна 15.
4. Во что это обходится
Время O(n). Каждый элемент один раз входит в окно и один раз уходит, то есть с ним делают два действия, какой бы ширины ни было окно. Память O(1): одна текущая сумма. Если складывать каждое окно заново, выйдет O(n·k). У простого способа цена растёт вместе с шириной окна, у скользящего окна не растёт.
5. Где это встречается
Так дашборды считают скользящее среднее (среднее по последним k значениям). В языке запросов к метрикам для этого есть функция avg_over_time. Торговые системы считают простое скользящее среднее цены. Системы, которые читают датчики, сглаживают шумные показания по окну фиксированного размера. Счётчики частоты считают события за последние k отрезков времени. Любая сводка по «последним k замерам», которая обновляется постоянно, использует прошлое окно и не пересматривает все числа заново.
windowStat([2, 1, 5, 1, 3, 2, 4], 3)Ищем самую большую сумму 3 чисел подряд. В окне всегда ровно 3 числа.
Столбики: 40 значений. Окно длиной 10, это четверть массива, и таблица ниже сохраняет эту долю.
Одна операция: одно чтение значения. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(n·k)O(n)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- непрерывный подмассив/подстрока заданной длины k
- каждое окно размера k
- скользящее среднее или скользящая сумма
- мин/макс/количество/сумма по каждому фиксированному отрезку
Похоже, но не то
- Скользящее окно (переменное) (Sliding window (variable))
Переменное окно само выбирает ширину по условию. Это окно на всём проходе шириной k.
- Префиксные суммы (Prefix sums)
Префиксные суммы строятся один раз и отвечают про любой диапазон. Окно отвечает про один движущийся отрезок.
- Монотонная дек-очередь (максимум/минимум окна) (Monotonic deque (sliding window max/min))
Сумма переживает вычитание, поэтому хватает арифметики. Максимуму нужна дек-очередь.
- Хеш-множество / словарь (Hash set / map)
Словарь считает по всей коллекции и не знает позиций. Окно спрашивает только про k соседей.
n до 1e6 при окне размера k даёт O(n). Каждый элемент один раз входит в окно и один раз выходит.
На LeetCode
Задачи про каждый отрезок ровно из k элементов подряд, например лучшую сумму, среднее или количество в окне размера k. Прибавляй элемент, который входит, и вычитай тот, что выходит.
Задача урока с одним лишним шагом, в конце раздели лучшую сумму на k.
- 1343.Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (откроется в новой вкладке)Средняя
Двигай сумму k чисел и считай окна, где сумма не меньше threshold * k.
Окно хранит число гласных вместо суммы, плюс один за вошедшую гласную и минус один за вышедшую.
Окно из 2k + 1 чисел с центром на каждом индексе, которое сдвигается на шаг за раз.
Твоя задача (Tier 1)
Напиши функцию maxWindowSum(nums, k).
Найди наибольшую сумму k чисел, стоящих подряд. Двигай окно размера k по списку и обновляй сумму на ходу, а не складывай её заново на каждом шаге.
- Вход:
nums, список чисел, иk, размер окна. Пример:[4, 2, 1, 7, 8],2. - Возвращает: наибольшую сумму любых
kчисел подряд. Если окно размераkне помещается в список, возвращаетnull(в Python это None).
Шаги:
- Если
kравно0, илиkбольше длины списка, или список пустой, верниnull. - Сложи первые
kчисел. Это сумма первого окна. Запомни её как лучшую. - Сдвигай окно по одному шагу до конца списка. На каждом шаге прибавляй новое число справа и вычитай число, которое ушло слева. Запоминай самую большую сумму из увиденных.
- Верни лучшую сумму.
Готово, когда проходят все тесты:
[4, 2, 1, 7, 8],2->15(7 + 8)[1, 1, 1, 1],2->2[5, 6],2->11(окно занимает весь список)[-1, -5, -2],2->-6(отрицательные числа допустимы)[-1, -5, -2],1->-1(самое большое отдельное число)[1, 2],5->null(kбольше длины списка)[],3->null(пустой список)[3, 4],0->null(kравно 0)
Практика
maxWindowSum
maxWindowSum(nums, k) -> number | null
export function maxWindowSum(nums, k) {
// Your code here. The task is described in the box above the editor.
}
Ты здесь как гость
Тесты запускаются прямо здесь, без аккаунта. Код сохраняется только в этом браузере. Бесплатный аккаунт сохранит его на любом устройстве, отметит шаг пройденным и покажет, где ты в курсе.
Лестница подсказок
Застрял? Открывай по одной, но сначала попробуй сам.