Как объявить и поддерживать максимум при сдвиге окна

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

Знаете ли вы монотонную очередь и можете ли объяснить, почему она даёт O(n), а не O(n·k). Для data-ml следом часто спрашивают, как сделать то же в pandas или на потоке событий.

Как отвечать

Наивный вариант, max(window) на каждом шаге, стоит O(n·k). Куча с ленивым удалением даёт O(n log k). Оптимум это дек индексов с инвариантом.

Что хранится и как поддерживается:

• индексы, а не значения: по индексу сразу видно, вышел элемент из окна или нет;
• убывание от головы к хвосту: значения по индексам в деке не возрастают, поэтому максимум окна всегда nums[dq[0]];
• вытеснение с хвоста: перед добавлением i снимаете с хвоста все индексы, чьё значение не больше nums[i]. Максимумом они уже не станут: новый элемент больше и проживёт в окне дольше;
• вытеснение с головы: если dq[0] <= i - k, индекс вышел из окна;
• выдача: максимум записывается, начиная с i >= k - 1.

Каждый индекс один раз попадает в дек и один раз из него уходит, поэтому суммарно O(n) по времени и O(k) по памяти. В Python нужен collections.deque: list.pop(0) сдвигает весь список, и выигрыш пропадает.

В рабочем коде это df['x'].rolling(k).max() в pandas, а для окна по времени rolling('5min') на DatetimeIndex. На потоке событий в деке хранят пары (метка времени, значение) и вытесняют голову по времени, а не по счётчику. Проговорите и крайние случаи: пустой вход, k == 1, k больше длины массива.

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

Хранят в деке значения вместо индексов и потом не могут объяснить, когда удалять голову. Для окна по времени такой вариант не работает вовсе.

Ошибаются на единицу в границах: условие dq[0] < i - k вместо <= оставляет в окне лишний элемент, а первый максимум пишется раньше, чем окно заполнилось.

Забывают про NaN. Любое сравнение с NaN ложно, он застревает в деке, и максимумы соседних окон превращаются в мусор. Пропуски выбрасывают или заполняют заранее, а в pandas помнят, что окно с пропуском даёт NaN, пока не задан min_periods.