問題と適用シナリオ
整数配列 nums とウィンドウサイズ k が与えられたとき、最初のウィンドウはインデックス 0 から k - 1 をカバーします。ウィンドウを一度に 1 ポジションずつ右へ動かし、各ウィンドウの最大値を返します。 制約は 1 <= nums.length <= 100000 および 1 <= k <= nums.length です。例えば以下のようになります。
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
result = [3, 3, 5, 5, 6, 7]目標は、出力配列を除いて O(n) 時間および O(k) の補助空間です。標準的な 問題では空でない配列と有効な k が保証されています。プロダクション API が空の配列や無効な k を受け入れる必要がある場合は、アルゴリズムの証明に未規定の動作を混在させるのではなく、 戻り値や例外を個別に定義してください。
2026 年に公開された複数の中国語および英語の面接対策リソースでは、現在もなお Sliding Window Maximum を 単調デックの典型演習として採用しており、先頭要素、期限切れインデックス、末尾からの削除、償却計算量の説明を 受験者に求めています。2026 年に公開された中国語の公開解法でも、全探索とデックによるアプローチを比較しています。 問われている本質的なスキルは一般的なアルゴリズムとデータ構造の推論力であるため、適切なカテゴリは coding です。 TypeScript による実装例が含まれていても、フロントエンド固有の問題になるわけではありません。
面接官が評価しているポイント
第 1 に、構造を認識できるかという点です。1 回の移動ごとに 1 つの要素が入り、1 つの要素が出ていく中で、 極値を常に取得可能にしておく必要があります。全探索では、隣接するウィンドウ間で共有される k - 1 個の要素を 再走査してしまいます。単調デックは、現在または将来の最大値になり得るインデックスのみを保持します。
第 2 に、デックに値単体ではなくインデックスを格納する理由を説明できるかという点です。期限切れ（ウィンドウ外への移動）は 位置に依存し、同じ値が異なる位置から現れることもあります。インデックスがなければ、先頭にある最大値が ウィンドウ外に出たかどうかを確実に判定できません。
第 3 に、末尾の要素を永久に削除してよい理由を証明できるかという点です。もし j < i かつ nums[j] <= nums[i] であるなら、より新しい要素は少なくとも同じ大きさであり、より遅くまでウィンドウ内に残ります。両方が同じ ウィンドウ内にある限り、古い要素が最大値になることはあり得ません。これは単にデックをソートされた状態に見せるための処理ではなく、 「支配（domination）」の論理によるものです。
最後に、計算量には償却解析が必要です。1 回の反復で複数のインデックスが削除されることがあるため、 個々の反復は厳密には O(1) ではありません。しかし、各インデックスは 1 度だけ挿入され、いずれかの端から 高々 1 度しか削除されないため、すべてのデック操作を合わせても O(n) 時間となります。
回答前に確認すべき明確化のための質問
- ウィンドウサイズは固定ですか？
kで固定です。可変ウィンドウの場合は、期限切れルールとクエリ仕様の再検討が必要です。 - 配列が空の可能性はありますか？ 標準の制約では除外されています。拡張 API の場合は、空配列を返すか入力を拒否するかを明示的に定義すべきです。
kは有効であることが保証されていますか？ 問題文では保証されています。サンプル実装では、無効な長さや範囲外アクセスを防ぐために実行時バリデーションを含めています。- 値の重複や負の値はあり得ますか？ はい。アルゴリズムは比較とインデックスのみに依存しており、正の値であることや一意性には依存しません。
- 等しい値がある場合、新しいインデックスと古いインデックスのどちらを残すべきですか？ どちらでも正しい最大値が得られます。本解法では古い等しい値を削除し、より遅く期限切れになるインデックスを残します。
- 補助空間は真に
O(k)である必要がありますか？ はい。古いスロットを回収せずに先頭ポインタだけを進める JavaScript 配列はO(n)のメモリを保持し続ける可能性があります。本解法では容量kの循環バッファを使用します。 - 戻り値は値ですか、それとも最大値のインデックスですか？ 本問では値を返します。インデックスが必要な場合は、先頭のインデックスを返し、重複する最大値のタイブレーク規則を定義します。
- 入力の変更は許可されていますか？ いいえ。実装は
numsを読み取るのみです。
30 秒の回答フレームワーク
「候補となるインデックスをデックで管理します。インデックスは先頭から末尾に向かって増加し、対応する値は 真に減少します。インデックス i では、まず先頭から期限切れのインデックスを削除します。次に、値が nums[i] 以下の間、末尾からインデックスを削除します。新しい要素は少なくとも同じ大きさで、かつ遅くまで残るためです。 i をプッシュした後、最初の完全なウィンドウが成立していれば、先頭の値が答えになります。各インデックスは 1 度プッシュされ、 高々 1 度削除されるため、全体の時間は O(n) です。デックには最大で k 個のインデックスが含まれるため、 補助空間は O(k) となります。」
ステップごとの詳細解説
ステップ 1: ベースラインとなるアプローチを用いて無駄な重複処理を特定する。
| アプローチ | 時間計算量 | 補助空間 | 主な課題 |
|---|---|---|---|
| 各ウィンドウを再走査 | O((n-k+1)k) | O(1) | 隣接するウィンドウ間で比較を重複して行う |
| インデックス付き最大ヒープと遅延削除 | O(n log n) | 最悪 O(n) | 期限切れエントリがトップに来るまで削除できない |
| 任意削除が可能な平衡二分探索木 | O(n log k) | O(k) | クエリに不要な完全な順序関係を維持してしまう |
| 単調デック | O(n) | O(k) | 将来最大値になり得るインデックスのみを保持する |
n と k が共に 100000 に近づくと、全探索は約 10^10 回の比較を行う可能性があります。ヒープは 有用な中間回答ですが、すべてのエントリ間の優先度を維持してしまいます。本問では最大値のみを取得するため、 より新しいエントリに支配された古い候補には将来の価値がありません。
ステップ 2: 支配（Domination）ルールを厳密に定義する。
j < i かつ nums[j] <= nums[i] と仮定します。両方のインデックスを含むすべての将来のウィンドウにおいて、 j の値が i の値を超えることはありません。ウィンドウが右に移動するにつれて、j は i よりも先に期限切れになります。したがって、i が現れた瞬間から、j が再びウィンドウの 最大値になることは決してなく、候補集合から恒久的に削除して問題ありません。
削除条件で「以下（less-than-or-equal）」を使用すると、等しい値に対して最も新しいインデックスのみが保持され、 デック内の値は真に減少（狭義の単調減少）します。厳密に小さい値のみを削除する方針も正当ですが、その場合の値は 単に非増加（広義の単調減少）となり、等しい候補が複数残ることになります。証明とコードは同一の戦略に従う必要があります。
ステップ 3: 検証可能な 4 つの不変条件を維持する。
インデックス i の処理後：
- デック内のインデックスは真に増加し、到着順に従っている。
- 格納されているすべてのインデックスは、現在の範囲
[i - k + 1, i]内にある。 - 対応する配列の値は、先頭から末尾に向かって真に減少している。
- 現在のウィンドウから削除されたすべてのインデックスは、その支配関係の連鎖上に、より新しく小さくない候補が残っている。
最初の 3 つの性質により、先頭要素が保持されている候補の中で最大であることが保証されます。4 つ目の性質は、 破棄された要素の中に真の最大値になり得たものが存在しないことを示します。これらが組み合わさることで、 先頭が単にデック内の最大要素であるだけでなく、ウィンドウ全体を代表する最大値であることが証明されます。
ステップ 4: 真に O(k) 空間を使用する循環デックを実装する。
export function maxSlidingWindow(
nums: readonly number[],
k: number,
): number[] {
if (!Number.isInteger(k) || k < 1 || k > nums.length) {
throw new RangeError("k must be an integer between 1 and nums.length");
}
const deque = new Int32Array(k);
let head = 0;
let size = 0;
const result: number[] = [];
for (let i = 0; i < nums.length; i += 1) {
while (size > 0 && deque[head] <= i - k) {
head = (head + 1) % k;
size -= 1;
}
while (size > 0) {
const back = (head + size - 1) % k;
if (nums[deque[back]] > nums[i]) break;
size -= 1;
}
deque[(head + size) % k] = i;
size += 1;
if (i >= k - 1) {
result.push(nums[deque[head]]);
}
}
return result;
}循環バッファは正確に k 個のスロットを持ちます。プッシュの前に期限切れエントリが削除されるため、 新しい要素を書き込む前の現在のウィンドウには最大で k - 1 個の有効なインデックスしか含まれず、プッシュによって 先頭が上書きされることはありません。Int32Array は、提示された最大値 100000 までのインデックスを格納できます。 32 ビットの範囲を超えるインデックスを許容する変形問題の場合は、通常の数値配列を使用するか、入力仕様を変更してください。
ステップ 5: 報告される各値がウィンドウの真の最大値であることを証明する。
デックは空の状態で開始するため、すべての不変条件が成り立ちます。新しいインデックスが到着した際、先頭からの削除では 現在のウィンドウ外の要素のみが破棄されます。末尾からの削除では支配ルールが適用され、削除された各要素は より新しく小さくないインデックス i に置き換えられます。i をプッシュすることで、増加するインデックスと 真に減少する値が維持されます。
最初の完全なウィンドウは i = k - 1 で成立します。それ以降、先頭は常にウィンドウ内に存在します。 デックの値が真に減少しているため、先頭は保持されている他のすべての候補よりも大きく、支配連鎖によって 保持されていないすべての要素は、いずれかの保持候補以下であることが保証されます。したがって nums[deque[head]] が 現在の最大値となります。すべての i に対する帰納法により、すべての n - k + 1 個の出力が正しいことが証明されます。
ステップ 6: 重複値と期限切れの境界をトレースする。
例として、以下の各エントリは index:value です。
i=0 [0:1] no full window yet
i=1 [1:3] 3 dominates 1
i=2 [1:3, 2:-1] output 3
i=3 [1:3, 2:-1, 3:-3] output 3
i=4 [4:5] 1 expires; 5 dominates -1 and -3; output 5
i=5 [4:5, 5:3] output 5
i=6 [6:6] 6 dominates 5 and 3; output 6
i=7 [7:7] 7 dominates 6; output 7[4, 4, 4]（k = 2）の場合、2 つ目の 4 が 1 つ目の 4 を削除し、3 つ目の 4 が 2 つ目を削除します。 デックには常に最新のインデックスが含まれ、両方のウィンドウで正しく 4 が返されます。このケースは等しい値の 条件を確認し、値のみを格納する手法では期限切れを正しく追跡できない理由を示しています。
ステップ 7: 償却計算量を正確に示す。
2 つの while ループによって計算量が O(nk) に増加することはありません。各インデックスは 1 度プッシュされ、 削除後に再び戻ることはないため、先頭および末尾からの削除の合計回数は最大でも n 回です。全体の時間は O(n) です。循環デックには最大 k 個のインデックスが格納されるため、補助空間は O(k) です。出力は n - k + 1 個のエントリを持ちますが、通常は補助空間の解析からは除外されます。
ステップ 8: 差分テストにナイーブなオラクル（参照実装）を使用する。
固定テストケースとして、k = 1、k = n、すべて等しい値、真に増加・減少する配列、すべて負の値、 標準の混在例を網羅する必要があります。空の配列および k = 0 は無効な入力であり、RangeError をスローすべきです。 その上で、短いランダム配列と有効なランダム k を生成し、各ウィンドウを走査するナイーブな実装と出力を比較します。 ランダムテストでは、結果の長さと各ウィンドウの値の両方を検証する必要があります。
非常に小さい n や単一ウィンドウの場合、全探索による走査の方がコードが短くレビューも容易です。 言語が信頼性の高い標準デックを提供している場合は、その標準コンテナを使用するのが望ましいです。ここで循環バッファを取り上げているのは、 TypeScript 実装の物理的なメモリ上限を O(k) の解析結果と厳密に一致させるためです。
模範解答の例
「全探索ではウィンドウごとに k 個の要素を走査するため、最悪ケースで O(nk) となります。私は インデックスを管理する単調デックを使用します。インデックスは到着順に増加し、対応する値は先頭から末尾に向かって 真に減少するように保ちます。
インデックス i では、まず i - k 以下の先頭インデックスを期限切れとしてすべて削除します。 次に、値が nums[i] 以下である間、末尾からインデックスを削除します。新しい要素は少なくとも同じ大きさで、 より遅くまでウィンドウに残るため、それらの古い要素が再び最大値になることはないためです。i をプッシュし、 i >= k - 1 となった後は、先頭要素が現在の最大値となります。
正当性は 2 つの事実から導かれます。先頭から削除された要素はウィンドウ外にあり、末尾から削除された要素には、 より長生きするより新しく小さくない代替要素が存在する点です。保持されている値は単調減少するため、残った最大の 候補は先頭に位置します。各インデックスは 1 度入り、高々 1 度しか出ないため、全体の時間は O(n) です。 デックは最大 k 個のインデックスを格納するため、補助空間は O(k) となります。テストとしては k = 1、 k = n、重複値、単調配列、負の数をカバーし、ランダムケースを全探索のオラクルと比較します。」
よくある間違い
- デックに値のみを格納する → 期限切れ時に等しい値を区別できない → インデックスを格納し、値は配列から読み取る。
- 値の減少を維持しつつ、期限切れの先頭を削除しない → ウィンドウ外に出た古い最大値が残り続ける → 各反復で
i - kを用いて先頭をクリーンアップする。 - 期限切れ判定に
< i - kを使用する →i - kと等しいインデックスはすでにウィンドウの左外にある → 「以下（less-than-or-equal）」を使用する。 - ネストされた
whileループをO(nk)と呼んでしまう → 1 つのインデックスが何度も削除されることはない → 各インデックスが出入りするのは高々 1 回である事実を利用する。 shift()を使用して定数時間での削除を主張する → JavaScript では先頭削除時に配列要素のシフトが発生する可能性がある → 標準デック、先頭ポインタ、または循環バッファを使用する。- メモリを解放せずに先頭ポインタだけを進めて
O(k)空間だと主張する → 内部配列がO(n)まで拡大する可能性がある → 固定容量kの循環ストレージを使用する。 - 等値ルールと証明の不一致 → 狭義の単調減少と広義の単調減少の不変条件が混同される → 本解法では「以下」を用いて古い値を削除すると明記する。
- ヒープに値のみを格納する → 遅延削除でも期限切れエントリを特定できない → ヒープアプローチでもインデックスの格納が必須。
- 標準例しかテストしない →
k = 1の境界エラー、重複、単調減少配列の見落としが発生する → 固定の境界ケースとランダムオラクルを追加する。
フォローアップ質問と回答
フォローアップ 1: 古い等しい値を削除しても安全なのはなぜですか？
新しいインデックスは同じ値を持ち、必ずより遅く期限切れになります。両方を含むすべてのウィンドウにおいて、 どちらのインデックスも同じ最大値を提供します。古い方が先にウィンドウを出て、新しい方が期限切れになった後に 古い方が再び候補になることはありません。したがって、新しいインデックスのみを保持することは安全であり、デックのサイズを抑えられます。
フォローアップ 2: 結果に各最大値の「最初の出現」を含める必要がある場合はどうしますか？
古い等しい値を削除しないようにします。末尾からは厳密に小さい値のみを削除し、デック内の値を広義の単調減少にします。 これにより、先頭は現在のウィンドウ内で最も早く出現した最大値を保持します。最後の出現が必要な場合は、 本解法の「以下」による削除を維持します。タイブレークのルールは変わりますが、O(n) の計算量限界は変わりません。
フォローアップ 3: なぜ最大ヒープを使わないのですか？
値とインデックスを格納し、遅延削除を行うヒープは手軽で有効な解法です。 ただし、トップにない期限切れエントリは割り当てられたまま残るため、通常の二分ヒープは O(n) の空間に 肥大化する可能性があり、時間も O(n log n) かかります。任意削除が可能なインデックス付きヒープを用いれば O(n log k) 時間および O(k) 空間を達成できますが、実装が複雑になります。面接では、単調デックに 最適化する前の中間回答としてヒープを述べるのが有効です。
フォローアップ 4: すべてのウィンドウで最大値と最小値の両方が必要な場合はどうしますか？
2 つの独立したデックを維持します。最大値用には値が減少するデックを、最小値用には値が増加するデックを用意します。 各インデックスが各デックに出入りするのは依然として高々 1 回であるため、全体の時間は O(n) のままであり、 補助空間も O(k) のままです。
フォローアップ 5: クエリごとにウィンドウサイズが変化する場合はどうしますか？
両方の境界が右方向にのみ移動する場合は、現在の左境界を使用して期限切れインデックスを削除すれば、 単調デックがそのまま機能します。ウィンドウが左側に拡張する可能性がある場合、永久に破棄された候補が 再び範囲内に入る可能性があり、復元できなくなります。更新とクエリのパターンに応じて、平衡二分木、セグメント木、 またはオフラインの Range Maximum Query（RMQ）構造を使用してください。
フォローアップ 6: 無限のデータストリームをオンラインで処理するにはどうしますか？
到着するデータごとに増加するシーケンス番号を割り当て、同様の期限切れ処理と末尾削除手順を適用し、 k 番目の要素以降、新しいデータが到着するたびに先頭の値を出力します。最大で k 個の 候補インデックスと値を格納するため、メモリ使用量はストリーム全体の長さから独立します。順不同で到着する場合は、 イベント時間ウィンドウ、ウォーターマーク、遅延データポリシーが追加で必要になりますが、これは本問のソート済み配列モデルの範囲外です。
フォローアップ 7: このパターンは制約付き動的計画法（Bounded DP）にどのように拡張されますか？
現在の状態が自身のコストと直前 k 個の状態の最大値の和で表される漸化式では、DP の値で順序付けられた デックを維持します。先頭が遷移の最大値を提供し、期限切れは依然としてインデックスに依存します。比較対象が nums[i] から dp[i] に変わりますが、より新しく小さくない状態が古い状態を支配するという証明の論理は 全く同じです。