1. Идея

Нужно для каждого окна длины k быстро находить максимум.

Если для каждого окна отдельно просматривать все k элементов, получится O(nk), что слишком медленно при n до 2 * 10^5.

Ключевая идея — поддерживать специальную очередь индексов, в которой:

• индексы идут слева направо по времени;
• значения a для этих индексов идут по убыванию.

Такая структура часто называется монотонной очередью.

Тогда максимум текущего окна всегда находится в начале этой очереди.

2. Наблюдения

Наблюдение 1

Если пришёл новый элемент a[i], то все элементы справа в очереди, которые не больше a[i], больше никогда не понадобятся.

Почему?

Потому что:

• новый элемент стоит правее, значит он дольше останется в будущих окнах;
• новый элемент не меньше, значит для максимума он не хуже.

Следовательно, такие элементы можно удалить с конца очереди.

Наблюдение 2

Когда окно сдвигается, некоторые индексы выходят за его левую границу.

Если индекс в начале очереди меньше левой границы окна, его нужно удалить из начала.

Наблюдение 3

После этих двух действий:

• в очереди останутся только индексы элементов текущего окна;
• значения по этим индексам будут идти по убыванию.

Значит, первый индекс в очереди указывает на максимум окна.

3. Алгоритм

Будем обрабатывать массив слева направо.

Пусть dq хранит индексы кандидатов на максимум.

Для каждого i от 0 до n - 1:

1. Удаляем с конца очереди все индексы j, для которых a[j] <= a[i].
2. Добавляем индекс i в конец очереди.
3. Вычисляем левую границу текущего окна: left = i - k + 1.
4. Удаляем из начала очереди все индексы, которые меньше left, то есть уже вышли из окна.
5. Если окно уже имеет длину k, то есть i >= k - 1, записываем ответ: a[dq.front()].

4. Почему это работает

Докажем, что алгоритм действительно выводит максимум для каждого окна.

Что хранится в очереди

В очереди лежат только индексы элементов, которые:

• ещё не вышли из текущего окна;
• могут быть максимумом в одном из текущих или будущих окон.

Когда добавляется новый элемент a[i], мы удаляем с конца все индексы с значением не больше a[i].

Это корректно, потому что любой такой элемент:

• слабее или равен по значению;
• расположен левее i.

Значит, в любом будущем окне, где присутствуют оба элемента, выгоднее использовать i, а старый индекс уже не понадобится.

Почему максимум в начале

После удаления меньших элементов с конца значения в очереди идут по убыванию.

После удаления устаревших индексов из начала в очереди остаются только элементы текущего окна.

Следовательно:

• первый индекс принадлежит текущему окну;
• его значение не меньше значений всех остальных элементов в очереди.

Значит, именно a[dq.front()] — максимум текущего окна.

Почему ничего не пропускается

Каждый элемент:

• один раз добавляется в очередь;
• не более одного раза удаляется с конца;
• не более одного раза удаляется с начала.

Поэтому все нужные максимумы будут найдены, и работа останется линейной.

5. Сложность

Каждый индекс попадает в очередь один раз и удаляется из неё не более одного раза.

Итоговая сложность:

• по времени: O(n)
• по памяти: O(n)

6. Код на C++17

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    deque<int> dq;
    vector<long long> ans;

    for (int i = 0; i < n; i++) {
        while (!dq.empty() && a[dq.back()] <= a[i]) {
            dq.pop_back();
        }
        dq.push_back(i);

        int left = i - k + 1;
        while (!dq.empty() && dq.front() < left) {
            dq.pop_front();
        }

        if (i >= k - 1) {
            ans.push_back(a[dq.front()]);
        }
    }

    for (int i = 0; i < (int)ans.size(); i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << ans[i];
    }
    cout << '\n';

    return 0;
}

7. Код на Python 3

n, k = map(int, input().split())
a = list(map(int, input().split()))

dq = [0] * n
head = 0
tail = 0
ans = []

for i in range(n):
    while tail > head and a[dq[tail - 1]] <= a[i]:
        tail -= 1
    dq[tail] = i
    tail += 1

    left = i - k + 1
    while tail > head and dq[head] < left:
        head += 1

    if i >= k - 1:
        ans.append(str(a[dq[head]]))

print(" ".join(ans))