スライド最小値・スライド最大値
#2024-04-28 #スライド最小値 #スライド最大値 #アルゴリズム
目次
1. スライド最小値・スライド最大値とは こちら
2. 今回考える問題概要 こちら
3. $ O(NK)解法 こちら
4. $ O(N \log N)解法 こちら
5. $ O(N)解法 こちら
6. 最後に こちら
/icons/hr.icon
ここではスライド最小値・スライド最大値について紹介します（ほぼ個人的なメモかも...）
スライド最小値・スライド最大値とは？
スライド最小値・スライド最大値は配列の任意の区間に対しての最小値・最大値を$ O(N)で求めることができるアルゴリズムです。
例として以下の問題を考えてみます。
/icons/hr.icon
今回考える問題概要
問題文
長さ$ N \: (1 \leq N \leq 2 \times 10^5)の配列$ Aが与えられます。
連続する$ K個の区間全ての区間$ N - K + 1個に対して区間内の最大値を求めてください。
入力
$ N$ K
$ A_1 \enspace \ A_2 \enspace \dots \enspace A_N
制約
$ 1 \leq N \leq 2 \times 10^5
$ 1 \leq K \leq N
$ 1 \leq A_i \leq 10^9 \: (1 \leq i \leq N)
入力例
$ 10$ 3
$ 3 \enspace 1 \enspace 4 \enspace 1 \enspace 5 \enspace 9 \enspace 2 \enspace 6 \enspace 5 \enspace 3
出力例
$ 4 \enspace 4 \enspace 5 \enspace 9 \enspace 9 \enspace 9 \enspace 6 \enspace 6
/icons/hr.icon
解法
1. $ O(NK)解法
まずは愚直解について考えてみます。
各区間に対して$ O(K)で全探索をすれば良いので$ O(NK)で求めることができます。
code:python
# 入力を受け取る
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0*(N - K + 1) # 区間の最大値を管理する配列
# N - K + 1 個の区間の最大値を求める
for i in range(N - K + 1):
max_ = 0
# 連続する K 個の区間の最大値を求める
for j in range(i, i + K):
max_ = max(max_, Aj)
# i, i+K の max を ansi に入れる
ansi = max_
# 答えを出力する
print(*ans)
こんな感じで解くことができました。
これだと diff 自体は灰だと思います。
しかしこのままでは$ O(NK)かかってしまっているので、提出しても TLE になってしまいます。
そこでもう少し高速化できないかを考えてみます。
/icons/hr.icon
2. $ O(N \log N)解法
この問題の本質は区間の最大値・最小値をどのようにして高速に求められるかを問う所にあります。
「区間の最大値・最小値の取得」に関してはある程度競プロをやってきた方ならわかると思いますが、セグメントツリー や map で管理することができます。
Python では map がない（Sortedset などを用いる必要がある）ので今回はセグ木を用いて区間の最大値を取得してみます。
code:python
def segfunc(x: int, y: int) -> int:
return max(x, y)
class SegTree:
def __init__(self, segfunc, init_val, ide_ele):
self.segfunc = segfunc
self.ide_ele = ide_ele
self.num = 2 ** N.bit_length()
self.seg = self.ide_ele * 2 * self.num
for i in range(N):
self.segi+self.num - 1 = init_vali
for i in range(self.num - 2, -1, -1):
self.segi = self.segfunc(self.seg2 * i + 1, self.seg2 * i + 2)
def update(self, k, x):
k += self.num - 1
self.segk = self.segfunc(self.segk, x)
while k:
k = (k - 1) // 2
self.segk = self.segfunc(self.segk * 2 + 1, self.segk * 2 + 2)
def query(self, l: int, r: int) -> int:
if r <= l:
return self.ide_ele
l += self.num - 1
r += self.num - 2
res = self.ide_ele
while r - l > 1:
if l & 1 == 0:
res = self.segfunc(res, self.segl)
if r & 1 == 1:
res = self.segfunc(res, self.segr)
r -= 1
l = l // 2
r = (r - 1) // 2
if l == r:
res = self.segfunc(res, self.segl)
else:
res = self.segfunc(res, self.segfunc(self.segl, self.segr))
return res
N, K = map(int, input().split())
A = list(map(int, input().split()))
seg = SegTree(segfunc, A, -10**18)
ans = 0*(N - K + 1)
for i in range(N - K + 1):
# [i, i+K)の最大値を取得して ansi に入れる
ansi = seg.query(i, i + K)
print(*ans)
ここまで来ると難しいですね、diff 自体も 緑 を超えてくるのではないでしょうか。
セグ木で区間の最大値取得は$ O(\log N)で出来るため、全体計算量は$ O(N \log N)となります。
これだけで自分の経験上青 diff くらいまでだと困らないと思うのですが、これを更に高速化できるようなアルゴリズムがあります。
それが今回紹介する スライド最小値・スライド最大値 になります
このアルゴリズムを用いることでセグ木などで$ O(N \log N)かかった計算量から$ \log Nだけ落とすことができ、$ O(N)で求めることができます。
それでは以降で紹介していきます。
/icons/hr.icon
3. $ O(N)解法
まずはスライド最大値を実装する上で、自分の頭の中で考えていることを言語化してみます。
入出力例は下記のもので考えます。
入力例
$ 10$ 3
$ 3 \enspace 1 \enspace 4 \enspace 1 \enspace 5 \enspace 9 \enspace 2 \enspace 6 \enspace 5 \enspace 3
出力例
$ 4 \enspace 4 \enspace 5 \enspace 9 \enspace 9 \enspace 9 \enspace 6 \enspace 6
手順
1. queue を用意します。
2. 最初の$ K \:(=3)項に対して狭義単調減少な数列を作ります。
3. 2. の際に$ (a_i, i)のように index も管理しておくことで今見ている区間$ [i, i+K)に含まれる要素かどうかを判別します。
4. 協議単調減少な配列を作っているので、これまでの最大値$ =cntよりも新しく入ってきた$ A_{i}の方が大きい$ cnt \lt A_i場合、queue の中身をそれで置き換わるまで pop し続けます。
5. こんな感じにやってくといい感じに$ O(N)で全ての区間の最大値を取得することができます。
上記の入力例に対して、実際の挙動は以下のようになります。
$ \begin{array}{|c|c|} \hline i & queueの中身(A_i, i) \\ \hline 0 & (4, 2) \\ \hline 1 & (4, 2), (1, 3) \\ \hline 2 & (5, 4) \\ \hline 3 & (9, 5) \\\hline 4 & (9, 5), (2, 6) \\ \hline 5 & (9, 5), (6, 7) \\ \hline 6 & (6, 7), (5, 8) \\ \hline \end{array}
各$ iに対して queue の中に入っている最も左の要素がその区間の最大値になります。
code:python
from collections import deque
def SlideMaxAlgorithm(a: list, k: int) -> list:
n = len(a)
ans = -1 * (n - k + 1)
q = deque()
q.append((ak - 1, k - 1))
for i in reversed(range(k - 1)):
if q00 < ai:
q.appendleft((ai, i))
ans0 = q00
for i in range(1, n - k + 1):
if q01 < i:
q.popleft()
while q:
if q-10 <= ai + k - 1:
q.pop()
else:
break
q.append((ai + k - 1, i + k - 1))
ansi = q00
return ans
def main() -> None:
a = 3, 1, 4, 1, 5, 9, 2, 6, 5
print(SlideMaxAlgorithm(a, 3))
if __name__ == "__main__":
main()
/icons/hr.icon
最後に
スライド最小値は逆に狭義単調増加な数列を作っていくことで求めることができます。
中々に言語化が難しく苦戦しました...
code:python
from collections import deque
def SlideMinAlgorithm(a: list, k: int) -> list:
n = len(a)
ans = -1 * (n - k + 1)
q = deque()
q.append((ak - 1, k - 1))
for i in range(k - 1):
if ai < q00:
q.appendleft((ai, i))
ans0 = q00
for i in range(1, n - k + 1):
if q01 < i:
q.popleft()
while q:
if ai + k - 1 <= q-10:
q.pop()
else:
break
q.append((ai + k - 1, i + k - 1))
ansi = q00
return ans
def main() -> None:
a = 3, 1, 4, 1, 5, 9, 2, 6, 5
print(SlideMinAlgorithm(a, 3))
if __name__ == "__main__":
main()