スライド最小値, Sliding Window Minimum Algorithm
概要
以下の問題を解く実装
-
長さ \(N\) の数列 \(A\)
-
数列 \(A\) における、連続 \(K\) 個の(\(N-K+1\) 個の)各部分列について、最小値を計算
蟻本[1]に解説がある。dequeを用いて計算できる。
計算量
\(O(N)\)
実装
# N: 要素列の長さ
# A[i]: 列のi番目の要素
# L: 最小値を調べる長さ
from collections import deque
A = [...]
L = ...
ans = []
que = deque()
for i, a in enumerate(A):
while que and a <= que[-1][1]:
que.pop()
que.append((i, a))
ans.append(que[0][1])
if que and que[0][0] <= i+1-L:
que.popleft()
ans = ans[L-1:]Verified
-
AOJ: "DSL_3_D: Sliding Window - Sliding Minimum Elements": source (Python3, 1.77sec)