Help us understand the problem. What is going on with this article?

アルゴリズム 体操2

Find Maximum in Sliding Window

説明

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

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

Screen Shot 2019-11-30 at 4.43.41.png

step1

Window の三つの要素の中の最大値が 2
Screen Shot 2019-11-30 at 4.45.17.png

step2

一つずらして、Window の三つの要素の中の最大値が 3
Screen Shot 2019-11-30 at 4.48.23.png

step3

一つずらして、Window の三つの要素の中の最大値が 6
Screen Shot 2019-11-30 at 4.49.18.png

最終的に 2 3 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

Screen Shot 2019-11-30 at 4.17.08.png
Screen Shot 2019-11-30 at 4.17.22.png

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした