本稿の出発点: https://www.aceround.app/ja/blog/ai-coding-interview-assistant/

上記の記事で触れた「スライディングウィンドウ」を、Qiita向けに独立したアルゴリズム解説として実装し直します。本文・コード・図は本稿用のオリジナルです。

結論

長さ k の各区間の最大値を求める Sliding Window Maximum は、単調デックを使うと次の計算量で解けます。

時間計算量: O(n)
補助空間: O(k)
デックの先頭: 現在のウィンドウの最大値

要点は、デックに値そのものではなく添字を入れ、次の3条件を保つことです。

添字は先頭から昇順です。
対応する値は先頭から降順です。
現在のウィンドウ外の添字は残しません。

これらが成立すれば、先頭の添字が常に最大値を指します。

問題

配列 nums とウィンドウ幅 k が与えられます。左から右へ1要素ずつウィンドウを動かし、各区間の最大値を返します。

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3

[1,  3, -1]          -> 3
    [3, -1, -3]       -> 3
        [-1, -3, 5]   -> 5
            [-3, 5, 3]-> 5
                ...

result = [3, 3, 5, 5, 6, 7]

各ウィンドウを毎回走査すると O(nk) です。最大ヒープなら O(n log k) にできますが、ウィンドウ外の要素を遅延削除する管理が必要です。単調デックなら、各添字を高々1回追加し、高々1回削除するだけです。

単調デックの不変条件

新しい要素 nums[i] を処理するとき、次の順番でデックを更新します。

先頭から期限切れの添字 <= i - k を削除します。
末尾から nums[i] 以下の値を削除します。
添字 i を末尾へ追加します。
ウィンドウが完成していれば、先頭の値を答えへ追加します。

手順2で削除できる理由は、新しい要素の方が値が大きいか等しく、しかも後までウィンドウ内に残るからです。古い小さい要素が将来最大値になる可能性はありません。

同じ値に対して <= を使い、古い添字を捨てる点も重要です。最大値自体は変わりませんが、新しい添字だけを残すと期限切れ処理が単純になります。

TypeScript実装

JavaScriptの Array.shift() は先頭削除後の要素移動が発生し得ます。そこで、固定長の循環バッファで添字デックを実装します。デックの要素数は k を超えないため、容量も k で十分です。

class IndexDeque {
  private readonly buffer: Int32Array;
  private head = 0;
  private size = 0;

  constructor(capacity: number) {
    if (!Number.isInteger(capacity) || capacity <= 0) {
      throw new RangeError("capacity must be a positive integer");
    }
    this.buffer = new Int32Array(capacity);
  }

  get isEmpty(): boolean {
    return this.size === 0;
  }

  front(): number {
    if (this.isEmpty) throw new RangeError("deque is empty");
    return this.buffer[this.head]!;
  }

  back(): number {
    if (this.isEmpty) throw new RangeError("deque is empty");
    const index = (this.head + this.size - 1) % this.buffer.length;
    return this.buffer[index]!;
  }

  pushBack(value: number): void {
    if (this.size === this.buffer.length) {
      throw new RangeError("deque capacity exceeded");
    }
    const index = (this.head + this.size) % this.buffer.length;
    this.buffer[index] = value;
    this.size += 1;
  }

  popFront(): number {
    const value = this.front();
    this.head = (this.head + 1) % this.buffer.length;
    this.size -= 1;
    return value;
  }

  popBack(): number {
    const value = this.back();
    this.size -= 1;
    return value;
  }
}

function maxSlidingWindow(nums: readonly number[], k: number): number[] {
  if (!Number.isInteger(k) || k <= 0 || k > nums.length) {
    throw new RangeError("k must satisfy 1 <= k <= nums.length");
  }

  const deque = new IndexDeque(k);
  const maxima: number[] = [];

  for (let i = 0; i < nums.length; i += 1) {
    while (!deque.isEmpty && deque.front() <= i - k) {
      deque.popFront();
    }

    while (!deque.isEmpty && nums[deque.back()]! <= nums[i]!) {
      deque.popBack();
    }

    deque.pushBack(i);

    if (i >= k - 1) {
      maxima.push(nums[deque.front()]!);
    }
  }

  return maxima;
}

Bunで境界をテストする

正しく見える実装でも、重複値、降順、k = 1 で壊れることがあります。最低限、次のケースを通します。

import { describe, expect, test } from "bun:test";

describe("maxSlidingWindow", () => {
  test("canonical example", () => {
    expect(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)).toEqual([
      3, 3, 5, 5, 6, 7,
    ]);
  });

  test("keeps the newest index when values are equal", () => {
    expect(maxSlidingWindow([4, 4, 4], 2)).toEqual([4, 4]);
  });

  test("handles descending input", () => {
    expect(maxSlidingWindow([5, 4, 3, 2], 2)).toEqual([5, 4, 3]);
  });

  test("handles a window of one", () => {
    expect(maxSlidingWindow([2, -1, 8], 1)).toEqual([2, -1, 8]);
  });

  test("rejects an invalid window size", () => {
    expect(() => maxSlidingWindow([1, 2], 0)).toThrow(RangeError);
    expect(() => maxSlidingWindow([1, 2], 3)).toThrow(RangeError);
  });
});

実行結果です。

5 pass
0 fail

なぜO(n)なのか

内側に while が2つあるため、一見すると二重ループに見えます。しかし、1つの添字に注目すると次のどちらかです。

末尾から1回削除されます。
最大候補として残り、期限切れ時に先頭から1回削除されます。

追加は各添字につき1回、削除も各添字につき高々1回です。したがって、デック操作の総数は入力長に比例し、全体は O(n) です。

補助空間はデックが最大 k 個、出力を除けば O(k) です。

面接で説明する順番

コードから書き始めるより、次の順番で説明すると意図が伝わりやすくなります。

全探索は O(nk) と確認します。
「現在の最大候補だけを残したい」と述べます。
デック内の値を降順に保つ不変条件を示します。
期限切れを先頭から、支配された候補を末尾から削除します。
各添字が1回ずつ出入りするため O(n) と証明します。

単調デックは、最終コードよりも「なぜ候補を捨ててよいか」を説明できるかが本質です。Sliding Window Maximumを暗記問題ではなく、不変条件を設計する問題として捉えると、類題にも応用しやすくなります。