Sliding Window Maximum
整数の配列 nums とウィンドウサイズ k が与えられます。k 個の連続する値からなるウィンドウは左端から始まり、右端が最後の値に達するまで、一度に1つずつ右へ移動します。配列の長さが n の場合、左から右へ各位置でのウィンドウ内の最大値を返します。値の数は n-k+1 個です。
関数
- numsinteger-array
- 配列上をスライドするウィンドウ
- kinteger
- 各ウィンドウ内の値の数
- 戻り値integer-array
- 左端のウィンドウから右端のウィンドウまで、各ウィンドウの最大値
制約
1 ≤ k ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104- 結果には
nums.length-k+1個の値が含まれます。ウィンドウごとに1つずつ、左から右の順に並びます。
例
- 入力
- nums = [4, 2, 12, 3, 8, 5, 1]k = 3
- 出力
- [12, 12, 12, 8, 8]
- 説明
- 12 は最初の3つのウィンドウに含まれているため、それぞれの答えは 12 です。12 がウィンドウから外れた後、
[3, 8, 5]と[8, 5, 1]はどちらも最大値が 8 です。
- 入力
- nums = [-3, -1, -7, -2]k = 2
- 出力
- [-1, -1, -2]
- 説明
- 区間は
[-3, -1]、[-1, -7]、[-7, -2]です。2つの負の数のうち大きい方はゼロに近い方なので、-1、-1、-2となります。
- 入力
- nums = [6, 6, 1]k = 3
- 出力
- [6]
- 説明
kが配列の長さと等しい場合、ウィンドウは1つで、配列全体が対象になります。その最大値は6です。6の2つ目のコピーは、2つ目の答えにはなりません。
発展問題
末尾への値の追加、先頭からの値の削除、現在の最大値の読み取りを、それぞれ償却時間 O(1) で行えるキューを作れますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
各ウィンドウの最大値を見つけるためにすべての値を調べるには、ウィンドウごとに
kステップかかります。隣り合う2つのウィンドウを比較すると、左側から1つの値が出て、右側から1つの値が入るため、k-1個の値が共通しています。新しい値が入ると、ウィンドウ内にあるその値以下の古い値は、二度と最大値になりません。古い値が残っている後続のウィンドウには新しい値も必ず残り、その値は古い値以上だからです。そうした古い値は完全に捨ててしまってかまいません。
- 両端キューには、残す値のインデックスを保持し、値が先頭から末尾に向かって厳密に減少するようにします。新しいインデックスごとに、末尾からそれ以下の値を取り除いてからインデックスを追加し、先頭のインデックスがウィンドウから外れていたら削除し、先頭の値をウィンドウ内の最大値として読み取ります。
解説
隣り合うウィンドウはk-1個の値を共有するため、最大値を毎回再計算すると、ほとんどの作業が繰り返されます。しかし、最大値は元に戻せません。最大の値がウィンドウから外れたとき、ウィンドウをもう一度調べずに次に大きい値を見つける必要があります。単調デックは、最大値になり得る値だけを保持し、答えを先頭に置きます。
すべてのウィンドウをスキャンする
正しいが、最大のテストでは終わらない
考え方
各ウィンドウのk個の値を読み取り、その中で最大の値を保持します。各ウィンドウをすべて読み取るため、その最大値を見落とすことはありません。n-k+1個のウィンドウそれぞれでk回読み取る必要があり、最悪なのはkがnのおよそ半分のときです。n = 2 × 10^4、k = 10^4の場合、約10^4個のウィンドウそれぞれに10^4個の値があり、読み取り回数は10^8回になります。
アルゴリズム
startを0からn-kまでループします。nums[start]からnums[start+k-1]までの中で最大の値を取得します。- それを結果に追加し、ループの後に結果を返します。
def maxSlidingWindow(nums, k):
result = []
for start in range(len(nums) - k + 1):
# Read all k values of this window again
result.append(max(nums[i] for i in range(start, start + k)))
return result各側からの最大値を含むブロック
考え方
配列をk個ずつのブロックに分けます。インデックス0からk-1、次にkから2k-1、というように分け、kがnを割り切らない場合は、最後のブロックは短くなります。ウィンドウの長さはちょうどkなので、ブロック全体か、あるブロックの末尾と次のブロックの先頭を合わせたものになります。
そこで、fromStart[i]に、iが属するブロックの先頭からiまでの最大値を、toEnd[i]に、iからそのブロックの末尾までの最大値をあらかじめ計算しておきます。iから始まるウィンドウはi+k-1で終わります。toEnd[i]が左側を、fromStart[i+k-1]が右側をカバーするため、大きい方がウィンドウの最大値です。最初の例では、ウィンドウ[2, 12, 3]について、toEnd[1] = 12とfromStart[3] = 3を使うので、最大値は12です。
3回の走査で時間計算量はO(n)になります。その代わり、長さnの補助配列が2つ必要で、最初の答えを出す前に配列全体が必要です。
アルゴリズム
fromStartを左から右へ埋め、iがkの倍数のときはnums[i]から再開します。toEndを右から左へ埋め、最後のインデックスと、i+1がkの倍数になる位置でnums[i]から再開します。- 0 から
n-kまでのすべての開始位置iについて、toEnd[i]とfromStart[i+k-1]の大きい方を追加します。
def maxSlidingWindow(nums, k):
n = len(nums)
# Cut nums into blocks of k: indices 0..k-1, k..2k-1, and so on.
from_start = [0] * n # max from the start of i's block up to i
to_end = [0] * n # max from i up to the end of i's block
for i in range(n):
if i % k == 0:
from_start[i] = nums[i]
else:
from_start[i] = max(from_start[i - 1], nums[i])
for i in range(n - 1, -1, -1):
if i == n - 1 or (i + 1) % k == 0:
to_end[i] = nums[i]
else:
to_end[i] = max(to_end[i + 1], nums[i])
# A window [i, i+k-1] is the tail of one block plus the head of the next.
return [max(to_end[i], from_start[i + k - 1]) for i in range(n - k + 1)]インデックスの単調デック
考え方
インデックス j が i より前にあり、nums[j] ≤ nums[i] なら、j が再び最大値になることはありません。j を含む後続のウィンドウにはすべて i も含まれ、先にウィンドウから外れるのは i だからです。したがって、i が到着したら j を忘れてかまいません。
まだ忘れられていないインデックスを両端キューに保持します。i が到着したら、末尾から、その値が nums[i] 以下であるインデックスを取り除き、その後 i を追加します。残った値は先頭から末尾にかけて厳密に減少するため、先頭がウィンドウの最大値です。先頭のインデックスはウィンドウがそこを通り過ぎたときにも取り除く必要があるので、インデックスを格納します。最初の例では、インデックス5の時点で両端キューには12、8、5が入っています。12はインデックス 5 - 3 = 2 にあるため、ウィンドウから外れ、答えは8です。
各インデックスは1回追加され、取り除かれるのは最大1回です。両端キューの操作は最大でも 2n 回で、時間計算量は O(n) です。両端キューに保持されるインデックスは最大でも k 個です。
アルゴリズム
- 各インデックス
iについて、deque が空でなく、その末尾の値がnums[i]以下である間、末尾からインデックスを取り出します。 - 末尾に
iを追加します。 - 先頭のインデックスが
i-kと等しい場合、そのインデックスはウィンドウから外れているため、取り出します。 i ≥ k-1になったら、先頭のインデックスに対応する値を結果に追加します。
from collections import deque
def maxSlidingWindow(nums, k):
window = deque() # indices; their values strictly decrease from front to back
result = []
for i, x in enumerate(nums):
# A value at the back that is not bigger than x can never be a maximum again.
while window and nums[window[-1]] <= x:
window.pop()
window.append(i)
# The front index has slid out of the window on the left.
if window[0] == i - k:
window.popleft()
# From index k-1 on, every step completes a window; its maximum sits at the front.
if i >= k - 1:
result.append(nums[window[0]])
return result
落とし穴と境界ケース
- インデックスではなく値を格納すること。
[3, 1, 3]とk = 2の場合、2つ目の3が最初の3を取り除き、その後、去った値であるnums[0]と等しいため、自身も取り除かれます。 - 答えを早すぎたり遅すぎたりするタイミングで返すこと。最初のウィンドウが完成するのはインデックス
k-1で、結果にはちょうどn-k+1個の値が含まれていなければなりません。 i-kではなくi-k+1を期限切れにすること。そのインデックスは、まだウィンドウの先頭の値です。- デックに何か入っているか確認せずに、末尾の要素を読み取ること。
- ブロック方式で、最後のブロックが
kより短くなる場合があることを忘れること。右から左への走査では、各ブロックの末尾だけでなく、最後のインデックスでも再開しなければなりません。
よくある質問3
Sliding Window Maximum の時間計算量は何ですか？
単調両端キューによる解法はO(n)時間で実行されます。これは、各インデックスが一度だけ追加され、削除される回数も最大で一度だからです。両端キューが保持するインデックスは最大k個なので、結果に加えて必要な追加領域はO(k)です。
スライディングウィンドウの最大値はヒープで求められますか？
はい。値とインデックスのペアを最大ヒープに追加し、先頭を読み取る前に、インデックスがウィンドウの範囲外にある間は取り出します。これは O(n log n) 時間で実行でき、最大で n 個の要素を保持できます。デックのほうが高速で省スペースなのは、より大きな値が到着した時点で不要な値をすぐに削除するためです。
単調デックと単調スタックの違いは何ですか？
dequeの末尾は単調スタックのように機能します。値を追加する前に、その値によって不要になる要素を取り除きます。dequeには、古くなりすぎた値を取り出すための先頭側の出口が追加されています。次に大きい要素には有効期限がないため、スタックだけで十分です。比較を逆にすると、dequeで各ウィンドウの最小値を求められます。
def maxSlidingWindow(nums, k):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [4, 2, 12, 3, 8, 5, 1] k = 3
期待される出力
[12, 12, 12, 8, 8]