TypeScriptでスライディングウィンドウ最大値をO(n)で解く：単調デックの不変条件とテスト

配列の連続した長さ (k) の区間ごとに最大値を返す問題は、コーディング面接でも実務でもよく現れます。愚直に各区間を走査すると O(nk) ですが、**単調デック（monotonic deque）**を使うと O(n) にできます。

この記事では、JavaScript の shift() に頼らず、固定長リングバッファで実装します。最後にそのまま実行できるテストも付けます。

問題

nums と区間長 k が与えられたとき、各スライディングウィンドウの最大値を返します。

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
[5, 3, 6]   -> 6
[3, 6, 7]   -> 7

期待する結果は [3, 3, 5, 5, 6, 7] です。

なぜ単調デックなのか

各ウィンドウの最大値だけが必要です。ある値より右側に、それ以上の値があるなら、左側の小さい値が最大値になることはもうありません。そこで候補を次の不変条件で管理します。

1. デック内の index は前から後ろへ増加します。
2. 対応する値は前から後ろへ単調減少します。
3. 先頭の index は常に現在のウィンドウ内にあります。

この状態なら、先頭の値がそのまま最大値です。

値そのものではなく index を持つのが重要です。index があれば、先頭がウィンドウの左端より古いかを即座に判定できます。また、同じ値を処理するときは古い index を捨てて新しい index を残すため、比較は <= にします。

実装

Array.prototype.shift() は先頭以外の要素を詰め直すため、配列が大きい場合に意図しないコストになります。ここではサイズ k の Int32Array をリングバッファとして使い、先頭位置だけを動かします。

export 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");
  }

  // デックには nums の値ではなく index を保持します。
  const deque = new Int32Array(k);
  let head = 0;
  let size = 0;

  const indexAt = (offset: number): number =>
    deque[(head + offset) % k]!;

  const result: number[] = [];

  for (let right = 0; right < nums.length; right += 1) {
    const left = right - k + 1;

    // 1. 左端より古い index を先頭から除きます。
    while (size > 0 && indexAt(0) < left) {
      head = (head + 1) % k;
      size -= 1;
    }

    // 2. 現在値以下の候補は、今後最大値になれないため後ろから除きます。
    while (
      size > 0 &&
      nums[indexAt(size - 1)]! <= nums[right]!
    ) {
      size -= 1;
    }

    // 3. 現在の index を末尾に追加します。
    deque[(head + size) % k] = right;
    size += 1;

    // 最初の k 個がそろったら、先頭がこの区間の最大値です。
    if (left >= 0) {
      result.push(nums[indexAt(0)]!);
    }
  }

  return result;
}

処理を1ステップずつ追う

nums = [1, 3, -1, -3, 5]、k = 3 の先頭部分を追います。

• 1 を追加すると、デックは [0] です。
• 3 を追加するとき、1 は 3 以下です。将来の最大値候補になれないため除き、デックは [1] になります。
• -1 を追加すると、デックは [1, 2] です。先頭の値 3 が最初の答えです。
• -3 を追加すると、index 0 はすでにありません。デックは [1, 2, 3] で、答えは引き続き 3 です。
• 5 を追加するとき、末尾の -3、-1、3 はすべて 5 以下なので取り除きます。デックは [4] となり、答えは 5 です。

各 index は一度追加され、先頭または末尾から一度だけ削除されます。そのため、内側の while があっても全体の時間計算量は O(n) です。リングバッファの容量は k なので、追加の空間計算量は O(k) です。

実行できるテスト

次のテストでは、基本ケース、同値が連続するケース、k = 1、不正な k を確認します。

import { strict as assert } from "node:assert";

assert.deepEqual(
  maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3),
  [3, 3, 5, 5, 6, 7],
);

assert.deepEqual(
  maxSlidingWindow([4, 4, 4, 4], 2),
  [4, 4, 4],
);

assert.deepEqual(
  maxSlidingWindow([9, 8, 7], 1),
  [9, 8, 7],
);

assert.throws(
  () => maxSlidingWindow([1, 2], 3),
  RangeError,
);

実装で確認したいポイント

面接でこの解法を説明するときは、次の順で話すと伝わりやすくなります。

• 毎区間を走査する O(nk) の方法から出発します。
• 「右側により大きい値が来た小さい値」は候補から捨てられることを示します。
• index を保存して、期限切れの候補を先頭から除く理由を説明します。
• 各要素が最大で一度追加・一度削除されるため、合計で O(n) になると結論づけます。

単調デックは、最大値・最小値・直近の制約付き候補を扱うストリーミング処理にも応用できる、再利用性の高いパターンです。