Как оптимизировать поиск максимума в скользящем окне

Что проверяют

Знаете ли вы монотонную очередь и умеете ли обосновать её линейную сложность. Наивное решение за O(n·k) пишут все, разговор идёт о том, почему deque даёт O(n), хотя внутри цикла стоит while. В data-ml следом часто спрашивают, как это делается в pandas или numpy на реальных данных.

Как отвечать

Идея: в collections.deque храним индексы, а не значения, причём так, чтобы значения по ним убывали от головы к хвосту. На каждом шаге:

• выбрасываем устаревшее: если индекс в голове уже левее текущего окна, делаем popleft();
• выбрасываем бесперспективное: пока значение в хвосте меньше текущего, делаем pop(). Такой элемент уже никогда не станет максимумом, потому что текущий больше и проживёт в окне дольше;
• добавляем текущий индекс в хвост;
• снимаем ответ: как только окно заполнено, максимум лежит в голове, это nums[dq[0]].

Сложность O(n) амортизированно: каждый индекс добавляется один раз и удаляется не больше одного раза, поэтому суммарная работа всех while не превышает n. Память O(k).

Альтернативы полезно назвать с их ценой. Куча с ленивым удалением устаревших элементов даёт O(n log n). Блочный приём с префиксными и суффиксными максимумами по блокам длины k даёт O(n) без очереди. Разреженная таблица подходит, когда окна разной длины и запросов много: O(n log n) на подготовку и O(1) на запрос.

На практике в анализе данных алгоритм руками не пишут: в pandas есть Series.rolling(k).max(), в том числе по временному окну rolling('5min') при индексе типа datetime. Вариант numpy.lib.stride_tricks.sliding_window_view(a, k).max(axis=1) удобен, но это всё ещё O(n·k) операций, просто векторизованных.

Где спотыкаются

Кладут в очередь значения вместо индексов и потом не могут понять, когда элемент покинул окно.

Говорят, что сложность O(n·k) из-за вложенного while, и не могут объяснить амортизацию: считают худший случай одного шага вместо суммарной работы.

Забывают граничные случаи: пустой массив, окно длиннее массива, k равное единице. В pandas начало ряда будет NaN, пока окно не заполнится, если не задан min_periods.