Поддержание максимума в окне?
Порядок, придумал.
Создадим список максимальной длины w, в котором содержатся пары (index, value) и value нестрого убывает. Как устроен этот список — разберём позже.
Сначала список пуст. Сначала w раз проводим операцию «a[i] вошёл». Затем n−w раз — сначала «a[i−w] вышел», затем «а[i] вошёл». Каждый раз list.front — это индекс и значение макс. элемента.
Операция «a[i] вошёл». С конца списка удаляем все элементы, чей value меньше, чем a[i]. Затем прицепляем пару (i, a[i]) к концу.
Операция «a[i] вышел». Если в начале списка index=i, удаляем первый элемент. Иначе — ничего не делаем.
Почему O(n)? Единственное, где сложность неочевидна — удаление в операции «a[i] вошёл». Но удалений будет не больше, чем вставок, а их точно O(n) — так что никаких проблем.
Ну и на сладкое — как должен быть устроен список.
— Ограниченная длина (не более w).
— Удаление из начала.
— Вставка в конец.
— Удаление из конца.
Переберите знакомые структуры данных. Какая больше всего подходит? По-моему, кольцевая очередь.
Попробуйте здесь прочитать: e-maxx.ru/algo/stacks_for_minima