Task L.cpp

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

using namespace std;

void add_back(deque<int> &deq, int val){
    // Если в наше число, на которое сдвигаемся, будет меньше чем все остальные в очереди
    // то мы должны их будем удалить, так как наше число будет считаться минимальным,
    // в другом случае перед ним сохранится минимальное число для позции 'окна'.
    // Пример логики ниже кода.
    while (!deq.empty() && deq.back() > val){
        deq.pop_back();
    }
    // Добавляем в конец очереди наше число, на которое мы передвинулись.
    deq.push_back(val);
}

    // Данная функция нужна для того, чтобы удалять число, с которого мы здвинулись.
void del_front(deque<int> &deq, int val){
    if (deq.front() == val){
        deq.pop_front();
    }
}

void solve(){
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (int i = 0; i < n; i++){
        cin >> arr[i];
    }
    
    // Работа программы:
    deque<int> deq;
    
    // Ищем для 'окна' в начальном положении длины k, минимальное число в нем. 
    int i = 0;
    for (; i < k; i++){
        add_back(deq, arr[i]);
    }
    cout << deq.front() << ' ';

    // Двигаясь вправо ищем для всех остальных расположений 'окна' длиной k минимальное число в нем
    // Двигаться мы будем N - K раз.
    for (; i < n; i++){
        del_front(deq, arr[i - k]);
        add_back(deq, arr[i]);
        cout << deq.front() << ' ';
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    solve();
    return 0;
}

/*
    В чем логика функций add_back и del_front? 
    Представим вот такую последовательность, которую занимает наше окно k = 5:
    {1, 5, 7, 9, 12}
    Минимальный здесь будет 1
    Следующее число, на которое мы сдвинемся будет например 3.
    С помощью функции del_front мы удаляем из очереди наше самое первое число
    т.к. мы уходим с него и получаем {5, 7, 9, 12}
    
    А с помощью функции add_back, мы сразу ищем минимум для наего окна и добавляем
    в конец наше число.
    Т.к. мы сдвинулись на число 3, все остальные числа в очереди можно удалить
    Потому что они больше чем наше число, а по нашей логике, минимальное число
    у нас всегда будет находится первым, получая с помощью deque.front();
    В итоге мы будем иметь очередь {3}
    Нам уже не важно какие числа, стояли до этого так как мы нашли уже минимальное
    для новой позиции окна.
    
    За O(k) - мы найдем в начальном положении.
    В самом худшем случае Алгоритм будет работать за O(n) для нахождения во всех
    позициях окна.
*/