Sliding Window Minimum Algorithm

概要

以下の問題を解く実装

  • 長さ\(N\)の数列\(A\)

  • 数列\(A\)における、連続\(K\)個の(\(N-K+1\)個の)各部分列について、最小値を計算

蟻本[1]に解説がある。dequeを用いて計算できる。

計算量

\(O(N)\)

実装

// DequeSlide
// 数列x_1, ..., x_nについてx_i, ..., x_{i+k}の最小値を求める
// DequeSlide(n: 配列数, l: kの値)
// push: 値(x_j)を追加
// get: x_i, ..., x_{i+k}の最小値を取得
// debug: デバッグ用
template<class T>
class DequeSlide {
  T *data;
  int *deq;
  int n, l, s, t;
  int cur;

public:
  DequeSlide(int n, int l) {
    data = new T[n];
    deq = new int[n];
    this->n = n;
    this->l = l;
    s = t = cur = 0;
  }

  void push(T x) {
    if(s<t && deq[s] == cur-l) s++;
    while(s<t && data[deq[t-1]] >= x) t--;
    deq[t++] = cur;
    data[cur++] = x;
  }

  T get() {
    return data[deq[s]];
  }

  void debug() {
    cout << s << " " << t << " [";
    repl(i, s, t-1) {
      cout << " " << data[deq[i]];
    }
    cout << " ]" << endl;
  }
};

Verified

  • AOJ: "DSL_3_D: Sliding Window - Sliding Minimum Elements": source (C++11, 1.29sec)



1. プログラミングコンテストチャレンジブック [第2版] p.300