Sliding window minimum
(Mylib/Algorithm/sliding_minimum.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

Requirements

Notes

Problems

• Codeforces Round #574 (Div. 2) E. OpenStreetMap

References

Verified with

• test/aoj/DSL_3_D/main.test.cpp

Code

#pragma once
#include <deque>
#include <vector>

namespace haar_lib {
  template <typename T>
  std::vector<T> sliding_minimum(const std::vector<T> &a, int k) {
    const int n = a.size();
    std::deque<int> dq;
    std::vector<T> ret;

    for (int i = 0; i < k; ++i) {
      while (not dq.empty() and a[dq.back()] >= a[i]) {
        dq.pop_back();
      }

      dq.push_back(i);
    }

    for (int i = 0; i < n - k + 1; ++i) {
      while (dq.front() < i) {
        dq.pop_front();
      }

      ret.push_back(a[dq.front()]);

      while (not dq.empty() and i + k < n and a[dq.back()] >= a[i + k]) {
        dq.pop_back();
      }

      dq.push_back(i + k);
    }

    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/Algorithm/sliding_minimum.cpp"
#include <deque>
#include <vector>

namespace haar_lib {
  template <typename T>
  std::vector<T> sliding_minimum(const std::vector<T> &a, int k) {
    const int n = a.size();
    std::deque<int> dq;
    std::vector<T> ret;

    for (int i = 0; i < k; ++i) {
      while (not dq.empty() and a[dq.back()] >= a[i]) {
        dq.pop_back();
      }

      dq.push_back(i);
    }

    for (int i = 0; i < n - k + 1; ++i) {
      while (dq.front() < i) {
        dq.pop_front();
      }

      ret.push_back(a[dq.front()]);

      while (not dq.empty() and i + k < n and a[dq.back()] >= a[i + k]) {
        dq.pop_back();
      }

      dq.push_back(i + k);
    }

    return ret;
  }
}  // namespace haar_lib

Back to top page