移動最大

Question

可能重複コンピューティング：私は数値データの（大）配列を有する
Find the min number in all contiguous subarrays of size l of a array of size n

（サイズNを）で最大値を実行するアレイを計算したいです固定ウィンドウサイズw。

もっと直接的には、k >= w-1の新しい配列out[k-w+1] = max{data[k-w+1,...,k]}を定義できます（これはC++のように0ベースの配列を前提としています）。

N log(w)より良い方法がありますか？

[wに依存せずにNに線形のものがあることを望んでいますが、移動平均のようですが、それを見つけることはできません。 N log(w)については、例えばwの構造上でinsert()、delete()、extract_max()をlog(w)以下にするソートされたデータ構造で管理する方法があると思います。

ありがとうございました。

Answer 1

実際、ウィンドウサイズwに依存しないO（N）時間にこれを行うことができるアルゴリズムがあります。アイデアは、以下の操作をサポートして巧妙なデータ構造を使用することです：

• 構造に新しい要素を追加しエンキュー、
• 構造から最も古い要素を削除デキュー、
• Find-maxは構造体から最小要素を返しますが、取り除きません。

これは基本的に最大要素のアクセス（ただし削除ではない）をサポートするキューデータ構造です。驚いたことに、this earlier questionに見られるように、これらの操作のそれぞれが償却O（1）時間で実行されるようにこのデータ構造を実装することが可能です。その結果、この構造体を使用してw要素をエンキューし、必要に応じてfind-maxを呼び出しながら、別の要素をデキューしてエンキューし続けると、O（n + Q）時間だけがかかります。ここでQはあなたが作る質問。各ウィンドウの最小値を一度だけ気にすると、ウィンドウサイズに依存せずにO（n）になります。

希望すると便利です。

Answer 2

私は、リストでそれを行う方法を説明します：

L = [21, 17, 16, 7, 3, 9, 11, 18, 19, 5, 10, 23, 20, 15, 4, 14, 1, 2, 22, 13, 8, 12, 6] 

長N=23とW = 4と。 i=0からN-1へ

L1 = [21, 17, 16, 7, 3, 9, 11, 18, 19, 5, 10, 23, 20, 15, 4, 14, 1, 2, 22, 13, 8, 12, 6] 
L2 = [21, 17, 16, 7, 3, 9, 11, 18, 19, 5, 10, 23, 20, 15, 4, 14, 1, 2, 22, 13, 8, 12, 6] 

ループ：

はあなたのリストの二つの新しいコピーを作成します。iがWで割り切れない場合は、L1[i]をmax(L1[i],L1[i-1])に置き換えます。 i=N-2から0へ

L1 = [21, 21, 21, 21, | 3, 9, 11, 18, | 19, 19, 19, 23 | 20, 20, 20, 20 | 1, 2, 22, 22 | 8, 12, 12] 

ループ。 i+1がWで割り切れない場合は、L2[i]をmax(L2[i], L2[i+1])に置き換えてください。

L2 = [21, 17, 16, 7 | 18, 18, 18, 18 | 23, 23, 23, 23 | 20, 15, 14, 14 | 22, 22, 22, 13 | 12, 12, 6] 

次に、このリストL3がL2[i]がiと、次の範囲の最大値である、あなたが求めて移動する最大値であるL3[i] = max(L2[i]、L1[i + W - 1])

L3 = [21, 17, 16, 11 | 18, 19, 19, 19 | 23, 23, 23, 23 | 20, 15, 14, 22 | 22, 22, 22, 13] 

ように、長さN + 1 - WのリストL3を作ります垂直線とi + W - 1の間の範囲の最大値はl1[i + W - 1]です。