スライド最小値
(include/emthrm/dynamic_programming/slide_min.hpp)

• View this file on GitHub
• Last update: 2022-12-15 22:18:37+09:00
• Include: #include "emthrm/dynamic_programming/slide_min.hpp"

時間計算量

$O(N)$

仕様

名前	戻り値
template <bool IS_MINIMIZED = true, typename T> std::vector<T> slide_min(const std::vector<T>& a, const int len);	$A$ に対する長さ $\mathrm{len}$ のスライド最小値

参考文献

• https://satanic0258.github.io/snippets/data-structure/SlideMinimum.html
• https://ei1333.github.io/luzhiled/snippets/dp/slide-min.html

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/DSL_3_D/review/4967096/emthrm/C++17

Verified with

• 動的計画法/スライド最小値 (test/dynamic_programming/slide_min.test.cpp)

Code

#ifndef EMTHRM_DYNAMIC_PROGRAMMING_SLIDE_MIN_HPP_
#define EMTHRM_DYNAMIC_PROGRAMMING_SLIDE_MIN_HPP_

#include <deque>
#include <vector>

namespace emthrm {

template <bool IS_MINIMIZED = true, typename T>
std::vector<T> slide_min(const std::vector<T>& a, const int len) {
  const int n = a.size();
  std::vector<T> res(n - len + 1);
  std::deque<T> deq;
  for (int i = 0; i < n; ++i) {
    while (!deq.empty() &&
           !(IS_MINIMIZED ? a[deq.back()] < a[i] : a[deq.back()] > a[i])) {
      deq.pop_back();
    }
    deq.emplace_back(i);
    if (i + 1 >= len) {
      const int left = i + 1 - len;
      res[left] = a[deq.front()];
      if (deq.front() == left) deq.pop_front();
    }
  }
  return res;
}

}  // namespace emthrm

#endif  // EMTHRM_DYNAMIC_PROGRAMMING_SLIDE_MIN_HPP_

#line 1 "include/emthrm/dynamic_programming/slide_min.hpp"



#include <deque>
#include <vector>

namespace emthrm {

template <bool IS_MINIMIZED = true, typename T>
std::vector<T> slide_min(const std::vector<T>& a, const int len) {
  const int n = a.size();
  std::vector<T> res(n - len + 1);
  std::deque<T> deq;
  for (int i = 0; i < n; ++i) {
    while (!deq.empty() &&
           !(IS_MINIMIZED ? a[deq.back()] < a[i] : a[deq.back()] > a[i])) {
      deq.pop_back();
    }
    deq.emplace_back(i);
    if (i + 1 >= len) {
      const int left = i + 1 - len;
      res[left] = a[deq.front()];
      if (deq.front() == left) deq.pop_front();
    }
  }
  return res;
}

}  // namespace emthrm

Back to top page