スライディングウィンドウ

連続区間をずらし、新しく入る値と出る値だけで状態を更新します。ウィンドウ全体を毎回計算し直す必要がありません。

モードと入力例を変えて比較してください。オレンジは現在のウィンドウ、緑はこれまでの最良区間です。

時間計算量O(n)

固定長ウィンドウ加算と減算

可変長ウィンドウlを進めて条件を復元

固定長の場合

長さkの和を毎回計算するとO(nk)です。スライドでは2つの値だけが変わり、1回の加算と減算で更新できるためO(n)です。演算回数を比較してください。

rを広げ、重複なしなどの条件が崩れたら、再び満たすまでlを進めます。辞書や頻度配列で区間の状態を管理します。ここではlastに各文字の最新位置を保存し、重複の直後までlを一度に進めます。

よくある演習

連続k個の最大和・平均、重複なし最長部分文字列、最小被覆区間、異なる値がk種類以下の最長区間などがあります。各長さkのウィンドウの最大要素には単調デックを使います。