8.3 Минимум в скользящем окне

Скользящее окно — это подмассив фиксированной длины, который шаг за шагом сдвигается слева направо по массиву. Для каждого положения окна нужно быстро вычислять некоторую характеристику элементов внутри него. В этом разделе нас интересует минимум в скользящем окне, то есть наименьший элемент среди всех значений текущего окна.

Идея

Эту задачу удобно решать почти так же, как и задачу о ближайшем меньшем элементе. Мы будем поддерживать дек — очередь с возможностью добавления и удаления с обоих концов.

В деке хранятся кандидаты на минимум текущего окна в неубывающем порядке:

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

Почему это работает? Если справа пришёл новый элемент, который меньше какого-то элемента в хвосте дека, то тот старый элемент уже никогда не станет минимумом ни в этом окне, ни в следующих, пока новый элемент остаётся внутри окна. Значит, его можно безопасно выбросить.

Пошаговый пример

Рассмотрим массив:

4 2 6 3 5 1 7 2

Пусть размер окна равен 3.

Первое окно

Первое окно содержит элементы:

4 2 6

После обработки этих элементов в деке останутся кандидаты:

2 6

Минимум окна равен 2.

Сдвиг окна вправо

Теперь окно стало таким:

2 6 3

Новый элемент 3 меньше, чем 6, поэтому 6 удаляется из конца дека. После этого в дек добавляется 3:

2 3

Минимум всё ещё равен 2.

Ещё один сдвиг

Окно теперь:

6 3 5

Элемент 2 уже вышел из окна, поэтому он удаляется из начала дека. Новый элемент 5 просто добавляется в конец:

3 5

Минимум окна теперь равен 3.

Следующий шаг

Окно становится таким:

3 5 1

Новый элемент 1 меньше всех элементов в деке, поэтому 5 и 3 удаляются из конца. После этого дек содержит только:

1

Минимум окна равен 1.

Последнее окно

Последнее окно:

1 7 2

Элемент 2 добавляется в конец дека, потому что он больше 1:

1 2

Минимум окна остаётся равным 1.

Что хранить в деке

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

Пусть текущее окно — это отрезок [l, r].

Тогда при обработке нового индекса r нужно сделать три шага:

1. Удалить из конца дека все индексы, у которых значение в массиве не меньше нового.
2. Добавить индекс r в конец дека.
3. Если индекс в начале дека меньше l, удалить его из начала.

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

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {4, 2, 6, 3, 5, 1, 7, 2};
    int k = 3;

    deque<int> q; // храним индексы

    for (int i = 0; i < (int)a.size(); i++) {
        // удаляем элементы, которые не лучше нового
        while (!q.empty() && a[q.back()] >= a[i]) {
            q.pop_back();
        }

        q.push_back(i);

        // удаляем элементы, вышедшие из окна
        while (!q.empty() && q.front() <= i - k) {
            q.pop_front();
        }

        // когда окно уже набрало длину k, выводим минимум
        if (i >= k - 1) {
            cout << a[q.front()] << " ";
        }
    }

    cout << "\n";
}

Для данного примера программа выведет:

2 2 3 1 1

Именно это и есть минимумы окон:

• [4, 2, 6] -> 2
• [2, 6, 3] -> 2
• [6, 3, 5] -> 3
• [3, 5, 1] -> 1
• [5, 1, 7] -> 1
• [1, 7, 2] -> 1

Почему алгоритм быстрый

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

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

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

Значит, на все операции с деком суммарно уходит O(n) времени, где n — длина массива. Следовательно, весь алгоритм тоже работает за:

O(n)

Главное, что стоит запомнить

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

Именно поэтому задача решается линейно, что особенно важно при больших ограничениях.