Sliding Window (Maximum)
(dp/SlidingWindowMaximum.hpp)

• View this file on GitHub
• Last update: 2025-10-01 01:04:11+09:00
• Include: #include "dp/SlidingWindowMaximum.hpp"

概要

todo

計算量

todo

Code

template <class T>
vector<T> sliding_window_maximum(const vector<T> &a, int k) {
    int n = int(a.size());
    if (n < k) return {};
    deque<int> q;
    vector<T> res(n - k + 1);
    rep(i, k) {
        while (!q.empty() and a[q.back()] <= a[i]) {
            q.pop_back();
        }
        q.emplace_back(i);
    }

    rep(i, n - k + 1) {
        res[i] = a[q.front()];
        if (i == q.front()) q.pop_front();
        while (!q.empty() and a[q.back()] <= a[i + k]) {
            q.pop_back();
        }
        q.emplace_back(i + k);
    }

    return res;
}

#line 1 "dp/SlidingWindowMaximum.hpp"
template <class T>
vector<T> sliding_window_maximum(const vector<T> &a, int k) {
    int n = int(a.size());
    if (n < k) return {};
    deque<int> q;
    vector<T> res(n - k + 1);
    rep(i, k) {
        while (!q.empty() and a[q.back()] <= a[i]) {
            q.pop_back();
        }
        q.emplace_back(i);
    }

    rep(i, n - k + 1) {
        res[i] = a[q.front()];
        if (i == q.front()) q.pop_front();
        while (!q.empty() and a[q.back()] <= a[i + k]) {
            q.pop_back();
        }
        q.emplace_back(i + k);
    }

    return res;
}

Back to top page