Минимум на скользящем окне за O(n) через монотонную очередь (дек) — как это работает?

Идея монотонной очереди: храним в деке индексы элементов-кандидатов на минимум так, чтобы значения шли строго по возрастанию от головы к хвосту. Тогда минимум окна всегда в голове дека.

При добавлении нового элемента a[r] выкидываем с хвоста все элементы >= a[r]: они уже никогда не станут минимумом — новый элемент и меньше, и «свежее» (дольше проживёт в окне). При сдвиге окна выкидываем с головы индекс, вышедший за левую границу (<= r - k).

vector<int> slidingMin(const vector<int>& a, int k) {
    deque<int> dq; // индексы, значения возрастают от головы к хвосту
    vector<int> res;
    for (int r = 0; r < (int)a.size(); r++) {
        while (!dq.empty() && a[dq.back()] >= a[r]) dq.pop_back();
        dq.push_back(r);
        if (dq.front() <= r - k) dq.pop_front();
        if (r >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}

Сложность O(n) время, O(k) память.

Почему линейно (амортизация): каждый индекс добавляется в дек ровно один раз (push_back) и удаляется максимум один раз (pop_back или pop_front). То есть суммарное число операций над деком ≤ 2n, несмотря на то что внутренний while иногда удаляет много элементов за одну итерацию. Это классический амортизированный анализ методом «каждый элемент платит за своё удаление». Для максимума — поменяй >= на <=.