スライディングウィンドウ問題において、各ウィンドウ内の最大値を効率的に求めるには、双方向キュー（deque）を活用した単調キューというデータ構造が有効である。このアプローチにより、O(n)の時間計算量で解を導出できる。

双方向キューの特性と選択理由

通常のキュー（queue）は、要素の追加が末尾から、取り出しが先頭からのみ可能である。一方、双方向キュー（deque）は両端からの追加・削除が可能である。

この問題でdequeが必要となる理由は、以下の2つの操作を両端から行う必要があるからだ：

• 先頭からの削除：ウィンドウの範囲外になった要素（期限切れの最大値候補）を除去
• 末尾からの削除：新しく追加される要素よりも小さい値を除去（これらは永遠に最大値になれない）

アルゴリズムの核となる考え方

dequeには配列のインデックスのみを格納し、以下の不変条件を維持する：

• deque内のインデックスに対応する値は降順（大きい順）に並ぶ
• 先頭の要素が常に現在のウィンドウ内での最大値のインデックスとなる

処理の詳細

配列を先頭から走査しながら、各ステップで以下の処理を行う：

1. 期限切れ要素の削除

dequeの先頭にあるインデックスが、現在のウィンドウ範囲外にあるかどうかを確認する。ウィンドウサイズをkとすると、現在のインデックスをiとしたとき、dequeの先頭 <= i - k という条件で期限切れを判定できる。期限切れの場合、先頭から削除する。

2. 無意味な要素の削除

dequeの末尾にあるインデックスに対応する値が、現在処理中の値以下である場合、その要素は将来的に最大値になる可能性がない。なぜなら、現在の値の方が新しく、かつ大きいため、現在の値がウィンドウ内にある限り、末尾の要素が選ばれることはないからである。これをdequeが空になるか、末尾の値が現在値より大きくなるまで繰り返す。

3. 現在のインデックスを追加

現在のインデックスiをdequeの末尾に追加する。

4. 結果の記録

ウィンドウが完全に形成されたタイミング（i >= k - 1）で、dequeの先頭にあるインデックスに対応する値を結果配列に追加する。

なぜ末尾からの削除が重要か

deque内の中間に位置する小さな値を削除できない場合、dequeは無限に膨張し、最終的にO(n²)の計算量となってしまう。末尾から「意味のない値」を削除することで、dequeのサイズを適切に保ち、全体の計算量をO(n)に抑えることができる。これは通常のキューでは実現不可能な操作である。

実装例

#include <iostream>
#include <vector>
#include <deque>

std::vector<int> findWindowMax(const std::vector<int>& data, int windowSize) {
    std::vector<int> result;
    std::deque<int> monoQueue;  // インデックスを格納する単調減少キュー

    for (int currIdx = 0; currIdx < data.size(); ++currIdx) {
        // ステップ1: ウィンドウ外の要素を先頭から削除
        int windowStart = currIdx - windowSize;
        while (!monoQueue.empty() && monoQueue.front() <= windowStart) {
            monoQueue.pop_front();
        }

        // ステップ2: 現在値以下の要素を末尾から削除
        while (!monoQueue.empty() && data[monoQueue.back()] <= data[currIdx]) {
            monoQueue.pop_back();
        }

        // ステップ3: 現在のインデックスを追加
        monoQueue.push_back(currIdx);

        // ステップ4: ウィンドウ形成後に最大値を記録
        if (currIdx >= windowSize - 1) {
            result.push_back(data[monoQueue.front()]);
        }
    }

    return result;
}

int main() {
    std::vector<int> input = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;

    std::vector<int> output = findWindowMax(input, k);

    std::cout << "結果: ";
    for (int val : output) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
    // 出力: 3 3 5 5 6 7

    return 0;
}

動作の可視化

入力配列 [1, 3, -1, -3, 5, 3, 6, 7]、ウィンドウサイズ k = 3 の場合：

このアルゴリズムは、各要素が最大で2回（追加時と削除時）dequeに触れるだけなので、全体の時間計算量はO(n)、空間計算量はO(k)となる。