0Pricing
Competitive Programming Academy · レッスン

Deque によるスライディングウィンドウ最大値

O(n) でウィンドウ内の極値を保ちます

「Deque によるスライディングウィンドウ最大値」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

スライディングウィンドウの最大値

配列とウィンドウサイズ k が与えられたとき、右に移動する各ウィンドウの最大値を求めます。素朴に行うと O(n × k) です。

より高速にできる理由

単調 deque を使えば、配列を一度走査するだけで、すべてのウィンドウを合計 O(n) 時間で処理できます。

ここでもインデックスを保存する

値ではなくインデックスを deque に保持します。インデックスがあれば、先頭が現在のウィンドウの外に出たか確認できます。

from collections import deque
dq = deque()
res = []

降順を保つ

deque は先頭から末尾に向かって値の降順を保ちます。そのため、先頭のインデックスは常にウィンドウの最大値を指します。

小さい末尾を削除する

インデックス i を追加する前に、末尾の値が小さい間は末尾から pop します。それらが将来の最大値になることはないためです。

while dq and nums[dq[-1]] <= nums[i]:
    dq.pop()

新しいインデックスを追加する

弱い末尾を取り除いたら、現在のインデックスをappendします。これで、次の処理に向けた deque の順序が保たれます。

dq.append(i)

古くなった先頭を追い出す

先頭のインデックスがウィンドウの外に出たら、popleft します。サイズ k のウィンドウは、インデックス i - k + 1 から始まります。

if dq[0] <= i - k:
    dq.popleft()

各最大値を記録する

インデックス k - 1 で最初の完全なウィンドウができた後は、deque の先頭が以降の各位置の答えを保持します。

if i >= k - 1:
    res.append(nums[dq[0]])

追い出す順序に注意する

答えを読み取る前に、古くなった先頭を追い出してください。そうしないと、すでにウィンドウから外れた最大値を報告する可能性があります。

線形時間になる理由

各インデックスは追加と削除を最大 1 回ずつ行うため、deque の処理は 1 ステップあたり償却 O(1)、全体で O(n) になります。

最小値でも同じ考え方

スライディングウィンドウの最小値を求める場合は、deque を昇順に保ちます。末尾を整理するときの比較を反転するだけです。

while dq and nums[dq[-1]] >= nums[i]:
    dq.pop()

確認問題

スライディングウィンドウの最大値を求めるとき、単調 deque の先頭は何を保持していますか。

まとめ：deque でウィンドウを処理する

インデックスの降順のdequeを保ち、小さい末尾を整理し、古くなった先頭を追い出して、各ウィンドウの最大値を先頭から O(n) で読み取りました。🏆

よくある質問

「Deque によるスライディングウィンドウ最大値」レッスンは無料ですか？

はい。「Deque によるスライディングウィンドウ最大値」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「Deque によるスライディングウィンドウ最大値」で何を学びますか？

O(n) でウィンドウ内の極値を保ちます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。

「Deque によるスライディングウィンドウ最大値」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 括弧の対応確認に使うスタック
  2. 単調スタック: 次に大きい要素
  3. キューと collections.deque
  4. Deque によるスライディングウィンドウ最大値
← Competitive Programming Academyに戻る