Sliding Window Minimum
(data-structure/slide_min.hpp)

• View this file on GitHub
• Last update: 2024-01-08 02:22:28+09:00
• Include: #include "data-structure/slide_min.hpp"

Description

スライド最小値は，全順序集合 $T$ を扱い，要素の最小値を求めることができるキューである．

Operations

• void push(T x)
  • $x$ をキューの末尾に追加する
  • 時間計算量: $\mathrm{amortized}\ O(1)$
• void pop()
  • キューの先頭要素を削除する
  • 時間計算量: $O(1)$
• T get()
  • キューの要素全体の最小値/最大値を返す
  • 時間計算量: $O(1)$

Verified with

• test/aoj/DSL_3_D.slide_min.test.cpp

Code

#pragma once
#include <deque>
#include <functional>
#include <utility>

template <typename T, typename Compare = std::less<>>
class SlideMin {
   public:
    void push(T x) {
        while (!dq.empty() && !cmp(dq.back().first, x)) dq.pop_back();
        dq.emplace_back(x, r++);
    }

    void pop() {
        if (dq.front().second == l) dq.pop_front();
        ++l;
    }

    T get() const { return dq.front().first; }

   private:
    int l = 0, r = 0;
    std::deque<std::pair<T, int>> dq;
    Compare cmp;
};

#line 2 "data-structure/slide_min.hpp"
#include <deque>
#include <functional>
#include <utility>

template <typename T, typename Compare = std::less<>>
class SlideMin {
   public:
    void push(T x) {
        while (!dq.empty() && !cmp(dq.back().first, x)) dq.pop_back();
        dq.emplace_back(x, r++);
    }

    void pop() {
        if (dq.front().second == l) dq.pop_front();
        ++l;
    }

    T get() const { return dq.front().first; }

   private:
    int l = 0, r = 0;
    std::deque<std::pair<T, int>> dq;
    Compare cmp;
};

Back to top page