スライディングウィンドウとは？
スライディングウィンドウ(Sliding Window)は、連続区間(ウィンドウ)を配列上で1つずつ滑らせ、区間和・最大値などの値をO(n)で保つ技法です。毎回区間を最初から計算するとO(nk)ですが、入る値を足し出る値を引いて更新すればO(n)に減ります。
核心の一行: 「重なる部分を再計算するな」。 1つ動いても区間の大部分はそのままです。
2種類のウィンドウ
- •固定サイズウィンドウ: サイズ
kが決まっていて、1つずつ右へ押します。「連続k個の最大和」のような問題。 - •可変サイズウィンドウ: 条件を満たすまで右端を広げ、条件が崩れたら左端を縮めます(尺取り法の同方向版)。「和がtarget以上の最小長」のような問題。
動作原理(固定サイズ)
ステップ1. 最初の k 個の和を先に計算します。
ステップ2. ウィンドウを右へ1つ押すとき、sum += arr[r](入った値)、sum -= arr[l](出た値)で更新します。
ステップ3. 移動のたびに最大値や条件を確認します。
可変ウィンドウなら、右を広げ続け、条件違反時に while で左を縮めて再び満たし、最適長を追跡します。
AlgoNoteの可視化は、ウィンドウが滑るときどの値が足され抜けるかをステップごとに示します。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(n) |
| 空間 | O(1) ~ O(k) |
各要素がウィンドウに一度入り一度出るので全体O(n)です。
例で追ってみる
[2, 1, 5, 1, 3, 2]、k = 3 の最大区間和:
- •最初のウィンドウ [2,1,5] = 8
- •1つ → +1 −2 → 7 ([1,5,1])
- •1つ → +3 −1 → 9 ([5,1,3]) ← 最大
- •1つ → +2 −5 → 6 ([1,3,2])
- •答え: 9
よくあるミス
- •出る値の引き忘れ: 入った値だけ足して抜けた値を引かないと、ウィンドウではなく累積和になります。
- •可変ウィンドウの境界: 左を縮めるとき
ifではなくwhileで条件を完全に回復します。 - •空ウィンドウ / k > n: 入力より大きいウィンドウなどの境界ケースを先に処理しましょう。
AlgoNoteで直接確認しましょう
ウィンドウが右へ滑るとき新しい値が足され古い値が抜け、区間値が更新される過程をAlgoNoteでステップごとに確認できます。