Скользящее окно
Вопрос
Что такое скользящее окно и когда оно применимо?
Попробуйте сами
Ответьте про себя или вслух, потом откройте ответ и сверьтесь.
Показать ответ и разбор
Коротко
Ответ
Отрезок [l, r] массива или строки, который двигается вправо: правый край добавляет элемент, левый убирает. Применимо к задачам про непрерывные подмассивы и подстроки, где состояние окна можно обновить за O(1) при добавлении и удалении элемента.
Разбор
Отрезок [l, r] массива или строки, который двигается вправо: правый край добавляет элемент, левый убирает. Применимо к задачам про непрерывные подмассивы и подстроки, где состояние окна можно обновить за O(1) при добавлении и удалении элемента.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.
Предыдущий вопрос
Почему вложенный while не даёт O(n²)
Следующий вопрос
Фиксированное и переменное окно
Термины по теме
Ещё по теме «Скользящее окно»
- Самая длинная серия единиц с k заменами
- Перестановка как подстрока
- Самая длинная серия после k замен
- Самая длинная подстрока без повторов
- Максимальная сумма окна длины k
- Максимум гласных в окне
- Кратчайший подмассив с суммой ≥ target
- Самая короткая подстрока с k различными