スライド最小値, 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)

戻る

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