Slide Min Algorithm
コードについての説明
数列 $a$(要素数 $n$), 正の整数 $k$ に対して $b[i] = \underset{i \le j < i+k}{\min} a[j]\ (0 \le i \le n-k)$ で定まる長さ $n-k+1$ の数列 $b$ を線形時間で求めるアルゴリズムがスライド最小値である.
実装は deque を用いて $a$ の要素を順番に後ろから詰めていき, $j < i$ (範囲外)となった $a[j]$ は deque の前から削除していく.
また deque に後ろから挿入する際に ($deq$ の最後の要素) $\ge$ (今入れる要素) が成り立つときは $deq$ の最後の要素が今後最小値を取ることが無いので後ろから削除する.
以上の操作を繰り返すことで線形時間で $b$ を構築することができる.
SilideMin$(Array, sz)$ : $res[i] = \underset{i \le j < i+sz}{\min} Array[j]\ (0 \le i \le n-sz)$ を満たす $res$ を構築する
時間計算量: $\O (n)$
コード
//長さnのArrayから連続k個の最小値の配列をresに格納
template <typename T> class SlideMin
{
public:
vector<int> deq;
vector<T> res;
int n,k;
SlideMin(const vector<T>& Array, int sz) : n((int)Array.size()), k(sz), deq(n), res(n-k+1){
int s = 0, t = 0;
for(int i = 0; i < n; i++){
//iを追加した場合に添字deq[t-1]の値がa[i]以上のときdeqから削除されるまで採用されることはないので
//最大値を取る場合は Array[deq[t-1]] <= Array[i] とする
while(s < t && Array[deq[t-1]] >= Array[i]){
t--;
}
deq[t++] = i;
if(i-k+1 >= 0){
res[i-k+1] = Array[deq[s]];
if(deq[s] == i-k+1){
s++;
}
}
}
}
};