スライド最大(最小)値とは
スライド最大(最小)値とは、
です。
解きたい問題
k年制の学校があり、在校生のうち一番頭の良い（数値の高い）人が生徒会長になります。
各年の生徒会長が誰になるかを考えてください。
普通に解くと各サブ配列の最大値を求めることになり、計算量はO(N^2)となってしまいます。
これをスライド最大値を使ってO(N)の計算量で解くことが可能です。
アルゴリズムの概要
全ての値を記憶しておくのではなく、最大になりうる値だけを残すようにします。
つまり、自分より大きい後輩がいる場合は最大になることはないのでその値を排除します。
次の年になると、最上級生が卒業して新入生が入ってきます。
在校生は新入生より値が小さい場合は、今後最大値にはなれないので削除します。
新入生は最大値になれる可能性があるのでそのまま追加されます。
残っている値の一番左のものが最大値となります。
在校生(window)の値全てを見て最大値を決める必要がなく、最大値の候補を新入生と比べるだけでいいので計算量が削減できました。
実装
卒業生はlistの左から出ていき、後輩より弱い在校生は右から出すような実装になるので、windowはdequeを使います。
from collections import deque
def sliding_window_max(nums, k):
window = deque()
max_num_in_window = []
for i in range(len(nums)):
if window and window[0] < i - k + 1:
window.popleft() # 卒業させる
while window and nums[window[-1]] < nums[i]:
window.pop() # 新入生より小さいものは削除する
window.append(i) # 新入生の追加
if i >= k - 1:
max_num_in_window.append(nums[window[0]])
return max_num_in_window
nums = [3, 9, 2, 1, 7, 5, 6, 8, 4]
k = 5
print(window_max(nums, k))
参考文献
コメント