【C++】サイズkの連続する部分配列それぞれの最大値を求める方法

問題の概要

n個の要素を持つ配列と値kが与えられたとき、サイズkの連続する部分配列（スライディングウィンドウ）それぞれにおける最大値を求めることを考えます。

例として、入力が arr = [3,4,6,2,8]、k = 3 の場合をみてみましょう。サイズ3の連続する部分配列は [3,4,6]、[4,6,2]、[6,2,8] の3つなので、それぞれの最大値である 6、6、8 が出力となります。

アルゴリズム：デック（deque）を使った効率的な解法

この問題は、両端キュー（デック）を利用することで効率的に解くことができます。手順は以下の通りです。

• デック Qi を用意し、まず最初のk個の要素を処理します
• 最初のウィンドウの処理（i = 0 から k-1 まで）：
  • Qiが空でなく、かつ arr[i] が Qi の末尾が指す要素以上である間、Qi の末尾の要素を削除します
  • その後、i を Qi の末尾に挿入します
• 残りの要素の処理（i = k から配列の末尾まで）：
  • Qi の先頭が指す要素（現在のウィンドウの最大値）を表示します
  • Qi の先頭のインデックスがウィンドウ範囲外（先頭 ≤ i - k）になったら、先頭の要素を削除します
  • Qiが空でなく、かつ arr[i] が末尾の指す要素以上である間、末尾の要素を削除します
  • i を Qi の末尾に挿入します
• 最後に、最後のウィンドウの最大値 arr[Qi.front()] を表示します

この手法では、各要素がデックに追加・削除されるのは高々1回ずつのため、全体の計算量は O(n) となり、単純な全探索（O(n×k)）よりも大幅に高速です。

C++での実装例

以下に実際の実装コードを示します。

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int main(){
    vector<int> arr = {3,4,6,2,8};
    int k = 3;
    deque<int> Qi(k);
    int i;
    for (i = 0; i < k; ++i){
        while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
            Qi.pop_back();

        Qi.push_back(i);
    }
    for ( ; i < arr.size(); ++i){
        cout << arr[Qi.front()] << " ";
        while ( (!Qi.empty()) && Qi.front() <= i - k)
            Qi.pop_front();
        while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
            Qi.pop_back();
        Qi.push_back(i);
    }
    cout << arr[Qi.front()] << endl;
}

実行結果

入力：

{3,4,6,2,8}, 3

出力：

6 6 8

ポイントの解説

このアルゴリズムの鍵となるのは、デックにはインデックスを降順の要素値で保持するという点です。デックの先頭には常に現在のウィンドウ内の最大値のインデックスが位置します。新しい要素が来たとき、それより小さい要素は将来ウィンドウ内で最大になることがないため、末尾から取り除いても問題ありません。また、先頭のインデックスがウィンドウから外れた場合は先頭から削除することで、常に有効な範囲の最大値を管理できます。