スライド最小値

蟻本を見ているとあまり知らないアルゴリズムが結構あったりするので、ちゃんと読み返しています。というわけでスライド最小値のメモ。

長さNの数列 a[i] に対して、長さkの連続部分列 {a[i], a[i + 1],... , a[i + k - 1]} の最小値を b[i] とします。この b[i] を 0 <= i <= n-k を満たすすべての i についてO(N)で計算できるテクがあります。

通常区間最小を高速に求めるにはSegment Tree等を使ってO(Nlog(N)) になります。ただ、Segment Treeは定数倍が遅いので高度な計算が必要ない場合は次のスライド最小値を使うほうが早いです。

まずDeque(Qとする)を用意します。このQに対し、a[i]を次のようにpushします。

1. Q の末尾からみていって、a[Qの末尾の要素] < a[i] となるまで Q の末尾をpopする

2. Qにi (値のa[i]ではなく、インデックスのi) をpush する

3. Qの先頭の要素 == i - k ならば先頭の要素を削除する

このQの要素をQ[i] とおくと、直感的に言えば、a[i]の長さKの連続部分列の中の単調増加(連続とは限らない)部分列のインデックスが入っている感じです。正確には次のようなQueueになっています

1. Q[0] < Q[1] < ... < Q[Qの最後]

2. a[Q[0]] < a[Q[1]] < ... < a[Q[Qの最後]]

3. Qの長さはK以下

そのため、今見ている区間でのb[i]はQ[0]で取得できます。Qの削除は追加した数N以上には発生しないため、計算量はO(N)となります。