しゃくとり法
以下の形式の問題を$ O(N)で解くことができる。
「条件」を満たす区間 (連続する部分列) のうち、最小の長さを求めよ
「条件」を満たす区間 (連続する部分列) のうち、最大の長さを求めよ
「条件」を満たす区間 (連続する部分列) を数え上げよ
しゃくとり法が使える条件は「条件」を満たす区間が以下のどちらかの構造になっていること
区間 [left, right) が「条件」を満たすなら、それに含まれる区間も「条件」を満たす
区間 [left, right) が「条件」を満たすなら、それを含む区間も「条件」を満たす
リファレンス