アルゴリズム 体操２

Find Maximum in Sliding Window

説明

整数の配列とサイズ w のWindow が与えられた場合、Window (配列の一部)が配列全体をスライドするときに Window中の 現在の最大値を見つけます。

例

Window の Sizeが 3 で、スライディングしていく中で、すべての最大値を見つけてみましょう。

step1

Window の三つの要素の中の最大値が　２

step2

一つずらして、Window の三つの要素の中の最大値が　３

step3

一つずらして、Window の三つの要素の中の最大値が　6

最終的に　２　３　６　が入ったデータ構造を返せば良い。

Solution

Time Complexity: O(n)

すべての要素は、1回の走査で一度だけdequeからプッシュおよびポップされます。プッシュとポップはO(1)なので、
アルゴリズムはTime Complexity O(n)で機能します。

Space Complexity: O(w)

Window のサイズ分のリストを使うのでSpace Complexity は O(w)です。

大まかなアルゴリズムの流れ

このアルゴリズムでは、dequeデータ構造を使用して、ウィンドウ内の最大値を見つけます。
このデータ構造を使用する目的は、両端に対して、データを追加、削除といったプッシュおよびポップ操作がほぼ、
O（1）で機能する両端キューだからです。これがウィンドウとして機能をします。ここでの注意が二つ。
1. dequeに入れるのは配列の要素ではなく、要素のIndex。
2. dequeの先頭に最大値のIndexを、末尾にそれ以外のIndexを入れていく。

アルゴリズムの開始時には、dequeはかっらぽなので、最初のウィンドウサイズの分だけ要素のIndexを追加していく。

もし、追加する要素がdequeの後ろの要素よりも小さい場合、追加した要素は新しいdequeの末尾要素となります。
もし、追加する要素の方が大きい場合は、より大きい要素が見つかるまでdeque後ろ側から繰り返し要素をポップしていき、
新しく末尾として追加する要素をプッシュします。

ご覧のとおり、dequeは要素を降順で格納します。
dequeの先頭には、その特定のウィンドウの最大値のインデックスが含まれます。

ウィンドウが右に移動するたびに、次の手順を繰り返します。

1. もし、dequeの後ろ側の要素が現在の追加する要素よりも小さいまたは等しい場合、追加する要素よりも大きい要素のインデックスが出てくるまで要素をdequeから削除します。
2. 一つウィンドウをずらすと、値が現在のウィンドウに収まらなくなる場合に、先頭の要素インデックスを削除します。
3. ウィンドウの後ろに現在の要素のインデックスをプッシュします。

Code