ホーム > libalgo

スライド最小値

概要

スライド最小値を求めます.

実装

template <class T>
std::vector<int> slideMinimum(const std::vector<T> &a, int k) {
    int n = a.size();
    std::deque<int> deq;
    std::vector<int> res;
    for (int i = 0; i < n; i++) {
        while (deq.size() && a[deq.back()] >= a[i]) deq.pop_back();
        deq.push_back(i);
        if (i - k + 1 >= 0) {
            res.push_back(deq.front());
            if (deq.front() == i - k + 1) deq.pop_front();
        }
    }
    return res;
}

参考文献

蟻本