Sliding Window Maximum
整数の配列 nums とウィンドウサイズ k が与えられます。ウィンドウは連続する k 個の値をカバーします。配列の左端から始まり、右端が最後の値に重なるまで、一度に1つずつ右へ移動します。
左から右へ、各位置のウィンドウ内の最大値を含む配列を返してください。長さ n の配列には n-k+1 個のウィンドウがあるため、結果は n-k+1 個の値を含みます。
関数
- numsinteger-array
- 配列をスライドしていくウィンドウ
- kinteger
- 各ウィンドウ内の値の数
- 戻り値integer-array
- 各ウィンドウの最大値を、最も左のウィンドウから最も右のウィンドウへ順に
制約
1 ≤ k ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104- 結果には、ウィンドウごとに1つずつ、左から右の順に
nums.length-k+1個の値が含まれます。
例
- 入力
- nums = [4, 2, 12, 3, 8, 5, 1]k = 3
- 出力
- [12, 12, 12, 8, 8]
- 説明
- 12は最初の3つのウィンドウ、
[4, 2, 12]、[2, 12, 3]、[12, 3, 8]に含まれています。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つになるわけではありません。
提出時に隠しテスト+15件
発展問題
末尾への値の追加、先頭からの値の削除、現在の最大値の読み取りを、それぞれ償却時間 O(1) でサポートするキューを実装できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
各ウィンドウの最大値を調べるには、ウィンドウごとに
kステップかかります。隣り合う2つのウィンドウを比べてみましょう。左側から1つの値が抜け、右側から1つの値が入るため、k-1個の値が共通しています。新しい値が入ると、ウィンドウ内にあるそれより小さいか等しい古い値は、二度と最大値になることはありません。古い値を含む後続のウィンドウには新しい値も含まれ、新しい値は少なくとも古い値と同じ大きさです。そうした古い値は完全に捨ててしまってかまいません。
- 両端キューに残る値のインデックスを保持し、値が先頭から末尾に向かって厳密に減少するようにします。新しいインデックスごとに、末尾から小さいか等しい値を取り除き、そのインデックスを追加します。先頭のインデックスがウィンドウの外に移動したら取り除き、先頭の値をウィンドウ内の最大値として読み取ります。
解説
隣り合うウィンドウは k-1 個の値を共有するため、最大値を毎回最初から計算すると、作業のほとんどが繰り返されます。難しいのは、最大値を取り消せないことです。左側から最大値が外れたとき、ウィンドウをもう一度読み直さずに次に大きい値を得る必要があります。単調両端キューは、まだ最大値になり得る値だけを順序どおりに保持するので、答えは常に先頭にあり、各インデックスは一度ずつ追加され、一度ずつ取り除かれます。
すべてのウィンドウをスキャンする
正しいが、最大のテストでは終わらない
考え方
最も直接的な考え方は、問題文に沿ったものです。インデックス start から始まるウィンドウは、start から start+k-1 までを含みます。その k 個の値を読み取り、最大値を保持して、開始位置を1つ右に移動します。開始位置は0から n-k までの n-k+1 個あります。
これは定義上正しい方法です。すべてのウィンドウを最初から最後まで読み取るため、その最大値を見落とすことはありません。結果とは別に必要な追加メモリは、現在の最大値を保持する1つの変数だけです。
ただし、処理は遅くなります。n-k+1 個ある各ウィンドウで k 回読み取るため、その積は k が n の約半分のときに最大になります。n = 2 × 10^4 かつ k = 10^4 の場合、10^4 個のウィンドウそれぞれで10^4個の値を読み取ることになり、合計で10^8回の読み取りです。さらに、隣り合う2つのウィンドウは k-1 個の値を共有するため、ほとんどの読み取りは、すでに読み取った値の再読み取りになります。
アルゴリズム
- 空の結果リストを作成します。
startを 0 からn-kまでループします。bestをnums[start]に設定し、次にnums[start+k-1]までのすべての値と比較して、大きい方を保持します。bestを結果に追加します。- 結果を返します。
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 までというように分け、n が k の倍数でない場合は、最後のブロックが短くなります。ウィンドウの長さはちょうど k なので、1つのブロックと一致するか、あるブロックの末尾と次のブロックの先頭にまたがります。3つのブロックにまたがることはありません。
ここから、2つの配列を使う方法が考えられます。fromStart[i] は、i の属するブロックの先頭から i までの最大値です。左から右へ埋め、各ブロックの先頭でリセットします。toEnd[i] は、i からそのブロックの末尾までの最大値です。右から左へ埋め、各ブロックの末尾でリセットします。i から始まるウィンドウは i+k-1 で終わります。その左側は toEnd[i] で、右側は fromStart[i+k-1] でカバーされるため、ウィンドウ内の最大値はこの2つのうち大きい方です。ウィンドウ全体が1つのブロックに収まる場合は、どちらの部分もそのブロックの最大値となるので、答えは正しく求まります。
nums = [4, 2, 12, 3, 8, 5, 1]、k = 3 の場合、ブロックは [4, 2, 12]、[3, 8, 5]、[1] です。fromStart は [4, 4, 12, 3, 8, 8, 1]、toEnd は [12, 12, 12, 8, 8, 5, 1] となります。ウィンドウ [2, 12, 3] はインデックス 1 から始まります。toEnd[1] = 12 が 2 と 12 をカバーし、fromStart[3] = 3 が 3 をカバーするので、答えは 12 です。
この方法の実行時間は O(n) で、配列を3回走査します。コストは長さ n の補助配列を2つ使うことで、最初のウィンドウの答えを出す前に配列全体が必要です。
アルゴリズム
fromStartを左から右へ埋めます。iがkの倍数ならnums[i]をコピーし、そうでなければfromStart[i-1]とnums[i]の大きい方を選びます。toEndを右から左へ埋めます。iが最後のインデックスであるか、i+1がkの倍数ならnums[i]をコピーし、そうでなければtoEnd[i+1]と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)]インデックスの単調両端キュー
考え方
まず、1つの観察から始めましょう。インデックス j がインデックス i より前にあり、nums[j] ≤ nums[i] だとします。j をまだ含む後続のウィンドウには、必ず i も含まれます。なぜなら、i はさらに右にあり、後になってウィンドウから外れるからです。そうしたウィンドウすべてで、nums[i] は nums[j] 以上なので、j が再び最大値になることはありません。i が到着した時点で、j は不要になるので、忘れてかまいません。
忘れていないインデックスを両端キューに保持します。i が到着したら、末尾から、値が nums[i] 以下のインデックスを取り除いてから、i を追加します。残ったインデックスの値は、先頭から末尾に向かって厳密に減少します。以前の値がそれより大きくなければ、すでに取り除かれているからです。したがって、先頭がウィンドウ内の最大値を持ちます。両端キューに値ではなくインデックスを格納するのは、ウィンドウが先頭の要素を通り過ぎたときに、それも取り除く必要があるからです。i で終わるウィンドウの開始位置は i-k+1 なので、外れるのはインデックス i-k です。それが先頭にあれば、取り除きます。
nums = [4, 2, 12, 3, 8, 5, 1] と k = 3 を使い、両端キュー内の値を追ってみましょう。4が入ります: [4]。2は小さいので、その後ろに入ります: [4, 2]。12は両方を取り除きます: [12]。最初のウィンドウの答えは12です。3が入ります: [12, 3]。答えは12です。8は3を取り除きます: [12, 8]。答えは12です。5が入ります: [12, 8, 5]。ただし、12はインデックス2にあり、インデックス5で終わるウィンドウの開始位置はインデックス3なので、12はすでにウィンドウから外れています: [8, 5]。答えは8です。1が入ります: [8, 5, 1]。答えは8です。
これが O(n) である理由: 内側のループでは1回の処理で複数のインデックスを取り除く場合がありますが、各インデックスが追加されるのは1回だけで、取り除かれるのも最大1回です。より大きな値に負けて末尾から取り除かれるか、ウィンドウから外れて先頭から取り除かれます。全体を通じた取り除きの回数は最大でも n 回なので、処理全体での両端キューの操作回数は最大 2n 回です。両端キュー内の各インデックスは現在のウィンドウ内にあるため、保持されるインデックスは最大でも k 個です。
アルゴリズム
- インデックスを格納する空の両端キューと、空の結果リストを作成します。
- 各インデックス
iについて、両端キューが空でなく、末尾の値がnums[i]以下である間、末尾からインデックスを取り出します。 iを末尾に追加します。- 先頭のインデックスが
i-kと等しい場合、そのインデックスはウィンドウから外れています。先頭から取り出します。 i ≥ k-1になったら、iで全幅のウィンドウが終了します。先頭のインデックスが指す値を結果に追加します。- 結果を返します。
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
落とし穴と境界ケース
ほとんどのバグは、ウィンドウの端の処理か、dequeに何を格納するかに起因します。
- インデックスではなく値を格納する。すると、先頭の値が
nums[i-k]と等しいときに削除することになりますが、重複値があると正しく動作しません。[3, 1, 3]でk = 2の場合、2つ目の3が最初の3を取り除き、その後、自身も削除されます。これは、ウィンドウから出た値と等しいためです。インデックスを格納し、先頭をi-kと比較してください。 - 答えを出すのが早すぎる、または遅すぎる。最初のウィンドウが完成するのはインデックス
kではなくk-1の時点であり、結果にはちょうどn-k+1個の値が入ります。 - 誤ったインデックスを削除する。インデックス
iで終わるウィンドウはi-k+1から始まるため、ウィンドウから出るのはインデックスi-kです。i-k+1を削除すると、まだウィンドウ内にある値が取り除かれます。 - 空のdequeの末尾や先頭を参照する。末尾と比較する前に、dequeに要素があることを確認してください。
- dequeをウィンドウのコピーとして扱う。dequeに入るのは候補だけで、インデックスの数は1から
kまで変わるため、そのサイズからウィンドウについては何も分かりません。 - ブロックを使う方法では、最後のブロックが
kより短くなる場合があることを忘れる。右から左への走査は、各ブロックの末尾だけでなく、最後のインデックスでも再開する必要があります。
よくある質問4
スライディングウィンドウ最大値の時間計算量はどれくらいですか？
単調デックを使う解法は、時間計算量が O(n) です。各インデックスは一度だけ追加され、取り出されるのは最大でも一度なので、1回のステップで複数の要素が取り出されることがあっても、全体を通して内側のループで取り出される回数は最大 n 回です。デックに保持されるインデックスは最大 k 個なので、結果に加えて必要な追加領域は O(k) です。
スライディングウィンドウの最大値はヒープで求められますか？
はい。値とインデックスのペアを最大ヒープに追加します。先頭を読み取る前に、インデックスがウィンドウの範囲外にある間はポップします。古いエントリは先頭に来たときにのみ削除されるためです。これは O(n log n) 時間で実行され、最大で n 個のエントリを保持できます。より大きな値が到着するとすぐに不要な値を削除するため、デックのほうが高速で省メモリです。
なぜdequeは値ではなくインデックスを格納するのでしょうか？
先頭要素はウィンドウがその位置を通り過ぎたら外す必要があり、それを判断できるのはインデックスだけです。値だけでは、nums[i-k]から推測するしかありませんが、同じ値が複数回現れる場合はうまくいきません。インデックスがあれば、追加のコストなしでnums[index]のように値も取得できます。
単調デックと単調スタックの違いは何ですか？
両端キューの末尾は単調スタックのように機能します。値を追加する前に、その値によって不要になる要素を取り除きます。両端キューでは、古くなりすぎた値を取り除くために、先頭にも出口が追加されます。次に大きい要素を求めるような、期限切れがない問題ではスタックだけで十分ですが、スライディングウィンドウでは両端を使います。比較の向きを逆にすれば、同じコードで各ウィンドウの最小値が求められます。
Python
def maxSlidingWindow(nums, k):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [4, 2, 12, 3, 8, 5, 1] k = 3
期待値
[12, 12, 12, 8, 8]