Sliding Window Minimum (スライド最小値)
(dp/sliding_window_minimum.hpp)

• View this file on GitHub
• Last update: 2023-02-06 19:40:21+09:00
• Include: #include "dp/sliding_window_minimum.hpp"

• 長さ $ n $ の数列 $ a $ と正整数 $k$ に対し、$ b_i = min { a_{i}, a_{i+1}, … , a_{i+k-1} } $ として定義される数列 $b$ を計算する
• $ O(n) $

お気持ち

• 1つ右端を進めたら1つ左端を進める、というイメージでアルゴリズムは進み、デックに入れる値が常に小さい順になるようにすることで、先頭の値が最小値になるようにしている

Verified with

• verify/aoj_dsl/aoj_dsl_3_d.test.cpp

Code

#pragma once

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

#line 2 "dp/sliding_window_minimum.hpp"

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

Back to top page