アルゴリズム 忘備録①

はじめに

最近、recursionというプログラミングサービスでコンピューターサイエンスの基礎を学習中でスライディングウィンドウが良く使われるアルゴリズムなので忘備録として書いてみました。

スライディングウィンドウアルゴリズムとは

例えば、サイズ4の連続する部分配列の最大値を求めるような問題で連続する部分配列があるとする、その部分配列の中で値をひとつづつ比較し最大値を求める方法だと計算量がo(n*k)と膨大になってしまいます。これをデキューを使うことによって計算量をo(n)に抑えることができるやり方です。

具体的には、デキューを用いて部分配列をひとつ前に進めてます。最初に部分配列に含まれていない値をポップし、新しく入ってきた値と既存のデキューの値を比べて新しく入ってきた値の方が大きいかデキューが空になるまでポップし続けるというものでそうすることでデキューの一番左にある値がその部分配列の中で最大であることが保証できます。

実際のコード(pythonでの実装)

maxWindowArrK.py

from collections import deque

def maxWindowArrK(intArr,k):
    # arrの要素がkより少ない場合、空のリストを返す
    if k > len(intArr): return []

    # 最大値を保持するためのリスト
    result = []
    # 値のインデックスを保持するデキュー
    deque_arr = deque()
    # デキューの初期化
    for i, num in enumerate(intArr[:k]):
        # デキューの末尾から比較し、新しい値(num)より小さいまたは等しい値をデキューから削除する。
        # これにより、デキューの末尾は新しい値よりも大きい値が保証されます。
        while len(deque_arr) > 0 and intArr[deque_arr[-1]] <= num:
            deque_arr.pop()
            
        # 現在のインデックス(i)をデキューの末尾に追加
        deque_arr.append(i)

    # ウィンドウをスライドさせていく
    for i, num in enumerate(intArr[k:], k):
        # デキューの先頭にあるインデックスの値は現在のウィンドウでの最大値
        result.append(intArr[deque_arr[0]])
        # ウィンドウから出た要素のインデックスがデキューの先頭にある場合、それを削除する
        while len(deque_arr) > 0 and deque_arr[0] <= i-k:
            deque_arr.popleft()
            
        # デキューの末尾から比較し、現在の値(num)より小さいまたは等しい値をデキューから削除する
        while len(deque_arr) > 0 and intArr[deque_arr[-1]] <= num:
            deque_arr.pop()

        # 現在のインデックス(i)をデキューの末尾に追加
        deque_arr.append(i)

    # 最後のウィンドウの最大値を追加
    result.append(intArr[deque_arr[0]])
    
    return result

# [64, 64, 64, 34, 14, 353, 353, 353, 353, 63]
print(maxWindowArrK([34,35,64,34,10,2,14,5,353,23,35,63,23], 4))