Код Senior Скользящее окно обновлено
Максимумы в окне
Условие
Для каждого положения окна длины k верни максимум. Если окно больше массива - пустой массив.
Примеры
slidingMax([1, 3, -1, 5, 7], 3) // [3, 5, 7]
slidingMax([1, 3, -1, -3, 5, 1, 1, 1, 2], 3) // [3, 3, 5, 5, 5, 1, 2]
slidingMax([], 3) // []
Как подойти
Наивное решение со slice и Math.max корректно, но квадратично. Монотонный дек даёт O(n): перед добавлением выбрасываем с хвоста всех, кто не больше нового - они уже никогда не станут максимумом. Из головы выбрасываем вышедших за окно. Каждый индекс входит и выходит один раз. Это тот же принцип, что и в монотонном стеке.
Подсказки: 3
- Пересчёт максимума на каждом шаге даёт O(n·k).
- Держи в очереди индексы, значения которых убывают.
- Голова очереди всегда максимум текущего окна.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.
Термины по теме
Ещё по теме «Скользящее окно»
- Самая длинная серия единиц с k заменами
- Перестановка как подстрока
- Самая длинная серия после k замен
- Самая длинная подстрока без повторов
- Максимальная сумма окна длины k
- Максимум гласных в окне
- Кратчайший подмассив с суммой ≥ target
- Самая короткая подстрока с k различными