Sliding Window Minimum Algorithm

概要

以下の問題を解く実装

  • 長さ\(N\)の数列\(A\)

  • 数列\(A\)における、連続\(K\)個の(\(N-K+1\)個の)各部分列について、最小値を計算

蟻本[1]に解説がある。dequeを用いて計算できる。

計算量

\(O(N)\)

実装

# N: 要素列の長さ
# A[i]: 列のi番目の要素
# L: 最小値を調べる長さ

from collections import deque
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)



1. プログラミングコンテストチャレンジブック [第2版] p.300