スライド最小値

sliding_window_minimum.py

from collections import deque
from collections.abc import Sequence
from numbers import Real
from typing import TypeVar

T = TypeVar("T", bound=Real)


def sliding_window_minimum(L: Sequence[T], K: int) -> Sequence[T]:
    """スライド最小値

    シーケンス L における長さ K の連続な部分列の最小値たちを算出する。
    セグメント木による RMQ を用いるなどで O(NlogN) の計算量での算出が可能ではあるが。
    L[0:K] と L[1:K+1] の違いは L[0] が取り除かれ L[K] が加わるにすぎない、
    そんな大半の過程が流用可能な状況下では deque を用いた O(N) 計算量の算出が可能。

    参照: プログラミングコンテストチャレンジブック 第2版 P.300
    参照: https://atcoder.jp/contests/abc352/submissions/53038335
    """
    min_values: list[T] = []
    que: deque[tuple[int, T]] = deque()

    for i, v in enumerate(L):
        # キューに値を追加する前に。
        while que and v <= que[-1][1]:
            # 値より大きい値が末尾に見つかった場合、取り除く。
            # これらは最小値候補になりえない
            que.pop()
        # キューの末尾に値を追加。
        que.append((i, v))
        # キューの先頭が求める最小値
        min_values.append(que[0][1])

        # キューの先頭が i+1-K 番目の場合、
        if que and que[0][0] <= i + 1 - K:
            # 次の対象区間の範囲外となるので取り除く
            que.popleft()

    # キューに K 個たまる前のデータは無効
    return min_values[K - 1 :]


def test_sliding_window_minimum_hand():
    L = [10, 5, 6, 7, 7, 3, 1, 4, 7]
    K = 3

    X = sliding_window_minimum(L, K)
    assert X == [5, 5, 6, 3, 1, 1, 1]


def test_sliding_window_minimum_random():
    import random

    generator = random.Random(20240505).random
    len_ = 10000
    L = [generator() for _ in range(len_)]
    for K in range(2, 10):
        X = sliding_window_minimum(L, K)
        Y = [min(L[i : i + K]) for i in range(len_ - K + 1)]
        assert X == Y