Задача

Есть довольно известная задача для заданного массива чисел и числа $$$K$$$ найти минимумы для всех отрезков длины $$$K$$$.

Более общий вариант: дан массив чисел длины $$$n$$$ и $$$q$$$ запросов о поиске минимума на отрезках $$$[l_i,r_i]$$$, причём $$$l_i \leq l_{i+1}$$$ и $$$r_i \leq r_{i+1}$$$. Решение должно работать за $$$O(n+q)$$$.

Решением задачи является поддержка скользящего окна, в котором хранится отрезок чисел. Нужна структура данных, умеющая в push_back (добавить элемент в конец окна), pop_front (удалить первый элемент окна) и get_min — текущий минимум.

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

Решение #1

Идея в том, чтобы хранить последовательность возрастающих минимумов. Первый элемент последовательности равен минимуму всего текущего окна, следом идёт минимум на суффиксе после этого элемента, и так далее. Например, для значений в окне [2,3,1,5,4,8,7,6,9] это будут минимумы [1,4,6,9].

Когда происходит добавление элемента справа (incR, push_back), последовательность меняется следующим образом: все большие элементы убираются, сам элемент добавляется в конец.

Несколько примеров, для [1,4,6,9]:

Добавление 5: [1,4,6,9] -> [1,4] -> [1,4,5]

Добавление 100: [1,4,6,9] -> [1,4,6,9,100]

Добавление 0: [1,4,6,9] -> [] -> [0]

При удалении элемента слева (incL, pop_front) нужно знать, был ли главный минимум первым элементом окна. По значению этого не понять, поэтому в последовательности помимо самих значений нужно хранить в паре с ними позиции этих значении. Пример выше превратится в последовательность [(1,2), (4,4), (6,7), (9,8)], если элементы нумеруются с нуля. Границы текущего окна нужно хранить явно в виде пары чисел $$$L$$$ и $$$R$$$. Итак, если первый элемент последовательности является первым элементом окна, то есть его позиция равна $$$L$$$, то его необходимо просто удалить, более ничего в последовательности не изменится.

Для реализации потребуется структура данных, позволяющая эффективно делать операции удаления слева и справа, а также добавления справа. Для этого можно использовать дек (std::deque в c++)

int inf = 2e9;
struct sliding_window{
    deque<pair<int,int>> d;
    int l, r;
    
    sliding_window(){
        l = r = 0;
    }
    
    void push_back(int x){
        while(!d.empty() && d.back().first >= x) d.pop_back();
        d.emplace_back(x,r);
        ++r;
    }
    
    void pop_front(){
        if(d.front().second == l) d.pop_front();
        ++l;
    }
    
    int get_min(){
        return d.empty() ? inf : d.front().first;
    }
};

Решение #2

Представим окно в виде двух стеков: префикс окна находится в левом стеке $$$L$$$ так, что первый элемент окна вверху $$$L$$$, а суффикс окна в правом стеке $$$R$$$ так, что последний элемент окна вверху $$$R$$$.

[2,3,1,5,4,8,7,6,9]
<-------|--------->

L = [5,1,3,2]
R = [4,8,7,6,9]

Когда происходит добавление элемента справа (incR, push_back), элемент попадает в вершину правого стека

При удалении элемента слева (incL, pop_front), элемент уходит с вершины левого стека. Исключение составляет случай, когда в этот момент левый стек пуст. Тогда перед удалением происходит операция перебрасывания правого стека в левый: пока правый стек не закончится, его верхний элемент перемещается в левый стек. Например,

[4,3,1,2]
|------->

L = []
R = [4,3,1,2]

L = [2]
R = [4,3,1]

L = [2,1]
R = [4,3]

L = [2,1,3]
R = [4]

L = [2,1,3,4]
R = []

[4,3,1,2]
<-------|

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

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

В левом стеке вместо самих значений нужно хранить минимум среди значений от этого элемента до дна стека. Например для стека [5,7,3,4,2,1,8,6] это будет стек [5,5,3,3,2,1,1,1]

Итого, минимум в окне будет равен либо верхнему элементу левого стека, либо $$$Rmin$$$.

int inf = 2e9;
struct sliding_window{
    vector<int> l, r;
    int rmin;
    
    sliding_window(){
        rmin = inf;
    }
    
    void push_back(int x){
        r.push_back(x);
        rmin = min(rmin, x);
    }
    
    void pop_front(){
        if(l.empty()){
            for(int mn = inf; !r.empty();){
                mn = min(mn, r.back());
                l.push_back(mn);
                r.pop_back();
            }
            rmin = inf;
        }
        l.pop_back();
    }
    
    int get_min(){
        int res = rmin;
        if(!l.empty()) res = min(res, l.back());
        return res;
    }
};

Примечание

Оба решения работают за одинаковую ассимптотику. Второе считаю более простым для понимания как алгоритм, но в первом меньше кода. Про сравнительное время работы ничего сказать не могу.

Также, оба решения можно проапгрейдить до операции push_front, хотя кажется, такая операция нигде не нужна.