Очередь с минимумом

По массиву движется окно, и на каждом его положении нужен минимум. Пересчитывать заново — $O(nk)$. Дек с правильным инвариантом даёт линию.

Инвариант

Держим дек индексов, значения по которым возрастают.

Новый элемент выбрасывает с хвоста всех, кто не меньше его: они уже никогда не станут минимумом, потому что новый и меньше, и правее — то есть переживёт их в окне.

С головы уходит индекс, вышедший за левую границу окна. Минимум всегда в голове.

deque<int> q;
for (int i = 0; i < n; i++) {
    while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();
    q.push_back(i);
    if (q.front() <= i - k) q.pop_front();
    if (i >= k - 1) cout << a[q.front()] << "\n";
}

По индексу, а не по значению

Самая частая ошибка — снимать с головы, сравнивая значения:

if (a[q.front()] == a[i - k]) q.pop_front();   // неверно

Таких значений в окне может быть несколько, и выбросится не тот. В деке лежат индексы именно для того, чтобы этого не случилось.

Две очереди сразу

Разброс окна — это максимум минус минимум, и для него нужны два дека с противоположными сравнениями.

Когда окно не фиксированной длины, а растёт, пока разброс допустим, голова снимается не по выходу за окно, а по сдвигу левой границы:

int left = 0;
for (int right = 0; right < n; right++) {
    while (!mx.empty() && a[mx.back()] <= a[right]) mx.pop_back();
    mx.push_back(right);
    while (!mn.empty() && a[mn.back()] >= a[right]) mn.pop_back();
    mn.push_back(right);

    while (a[mx.front()] - a[mn.front()] > limit) {
        if (mx.front() == left) mx.pop_front();
        if (mn.front() == left) mn.pop_front();
        left++;
    }
    best = max(best, right - left + 1);
}

Порядок «сначала добавить правый, потом чинить левый» здесь обязателен: он гарантирует, что деки не окажутся пустыми в момент обращения к голове.

Чем это отличается от кучи

Куча тоже отдаёт минимум, но за логарифм, и не умеет удалять «тот, что вышел из окна». Обходят это ленивым удалением: складывают в кучу пары «значение и индекс» и выбрасывают из головы всё, что уже вне окна.

Работает, но $O(n \log n)$ против $O(n)$ и с заметно большей константой. Дек лучше везде, где окно движется только вправо.

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