スライド最小値 - isee競プロメモ

スライド最小値

https://qiita.com/kuuso1/items/318d42cd089a49eeb332 この記事が感覚的にわかりやすかった。

概要

長さ$ N の配列で$ K 個からなる連続部分列それぞれの最小値を$ O(N) でまとめて求めるやつ

手順

dequeに「最小値になりうる値」を記録していく感じ。

追加・削除操作を以下のように定義する。

$ a を追加する操作

dequeの右端が$ a 以下になるまで右からpopしていく。

$ a より大きいやつらはもう最小値になり得ないので

dequeの右端に$ a を追加する

$ a を削除する操作

dequeの左端が$ a ならpopする。

dequeの左端が$ a じゃないなら何もしない。

この操作を使って以下を適度に繰り返す

$ i 個目を追加

最小値を記録

$ i - K + 1個目を削除

実装

返値先頭の$ K - 1 要素は$ K より短い区間についての計算結果になる

code:slidemin.py

def slideMin(L, K):

minq = deque()

res = []

for i, a in enumerate(L):

# i 個目を追加

while minq and minq-1 > a: minq.pop()

minq.append(a)

# 最小値を記録

res.append(minq0)

# i - K + 1 個目を削除

if i - K + 1 >= 0 and minq and minq0 == Li-K+1: minq.popleft()

return res

使用例