本稿の出発点: 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を暗記問題ではなく、不変条件を設計する問題として捉えると、類題にも応用しやすくなります。