Slide-Min - スライド最小値
(Library/unauthenticated/SlideMin.hpp)

• View this file on GitHub
• Last update: 2024-09-04 01:04:48+09:00
• Include: #include "Library/unauthenticated/SlideMin.hpp"

Code

/**
 * @file SlideMin.hpp
 * @author log K (lX57)
 * @brief Slide-Min - スライド最小値
 * @version 1.0
 * @date 2023-10-30
 */

#include <bits/stdc++.h>
using namespace std;

template<typename T>
vector<T> SlideMin(vector<T> A, int K){
    int N = A.size();
    deque<int> Q;
    vector<T> B;
    for(int i = 0; i < N; ++i){
        while(Q.size() and A[Q.back()] >= A[i]) Q.pop_back();
        Q.push_back(i);
        if(Q.front() == i - K) Q.pop_front();
        if(i - K + 1 >= 0) B.push_back(A[Q.front()]);
    }
    return B;
}

#line 1 "Library/unauthenticated/SlideMin.hpp"
/**
 * @file SlideMin.hpp
 * @author log K (lX57)
 * @brief Slide-Min - スライド最小値
 * @version 1.0
 * @date 2023-10-30
 */

#include <bits/stdc++.h>
using namespace std;

template<typename T>
vector<T> SlideMin(vector<T> A, int K){
    int N = A.size();
    deque<int> Q;
    vector<T> B;
    for(int i = 0; i < N; ++i){
        while(Q.size() and A[Q.back()] >= A[i]) Q.pop_back();
        Q.push_back(i);
        if(Q.front() == i - K) Q.pop_front();
        if(i - K + 1 >= 0) B.push_back(A[Q.front()]);
    }
    return B;
}

Back to top page