C++でスライディングウィンドウの最大値を求める方法

問題概要

nums という整数型の配列が与えられ、サイズ k のスライディングウィンドウが配列の左端から右端へ向かって移動していくとします。ウィンドウの中からは常に k 個の数値だけが見えており、ウィンドウは毎回 1 つずつ右に移動します。このとき、各位置におけるウィンドウ内の最大値を順番に求めるのが本問題です。

例として、入力が [1,3,-1,-3,5,3,6,8]、k = 3 の場合を考えてみましょう。ウィンドウの動きとそれぞれの最大値は次の表のようになります。

解法のアプローチ

この問題を効率的に解くには、両端キュー(deque)を活用する手法が有効です。各ウィンドウごとに素朴に最大値を計算すると O(n×k) の計算量が必要ですが、deque を使うことで配列全体をたった一度の走査(O(n))で処理できます。

ポイントは、deque に「インデックス」を格納し、対応する値が常に降順になるように維持することです。こうすることで、ウィンドウ内の最大値は常に deque の先頭にあることになります。

アルゴリズムの手順

• 結果を格納するための配列 ans を定義します

• インデックスを管理するための両端キュー dq を定義します

• nums のサイズが 0 の場合は、そのまま ans を返します

• i を 0 から k 未満まで 1 ずつ増やしながら以下を繰り返します:

  • dq が空でなく、nums[dq の末尾の要素] が nums[i] より小さい間、dq の末尾の要素を削除します

  • i を dq の末尾に挿入します

• i を k から nums.size() 未満まで 1 ずつ増やしながら以下を繰り返します:

  • nums[dq の先頭の要素](現在のウィンドウの最大値)を ans に追加します

  • dq が空でなく、dq の先頭の要素が (i − k + 1) より小さい場合(= インデックスがウィンドウの範囲外になった場合)、先頭の要素を削除します

  • dq が空でなく、nums[dq の末尾の要素] が nums[i] より小さい間、末尾の要素を削除します

  • i を dq の末尾に挿入します

• 最後に、nums[dq の先頭の要素] を ans の末尾に追加します

• ans を返します

C++での実装例

以下の実装例を見て、より深く理解しましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> maxSlidingWindow(vector<int>& nums, int k) {
      vector <int> ans;
      deque <int> dq;
      if(nums.size()==0)return ans;
      for(int i =0;i<k;i++){
         while(!dq.empty() && nums[dq.back()]<nums[i])dq.pop_back();
         dq.push_back(i);
      }
      for(int i = k;i<nums.size();i++){
         ans.push_back(nums[dq.front()]);
         while(!dq.empty() && dq.front()<(i-k + 1))dq.pop_front();
         while(!dq.empty() && nums[dq.back()]<nums[i])dq.pop_back();
         dq.push_back(i);
      }
      ans.push_back(nums[dq.front()]);
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,3,-1,-3,5,3,6,8};
   print_vector(ob.maxSlidingWindow(v,3));
}

入力

{1,3,-1,-3,5,3,6,8}

出力

[3, 3, 5, 5, 6, 8]

計算量の評価

このアルゴリズムの時間計算量は O(n) です。これは、各要素が deque に対して最大でも 1 回の挿入と 1 回の削除しか行われないためです。また、deque には同時に最大 k 個のインデックスしか保持されないため、空間計算量は O(k) となります。素朴な全探索アプローチの O(n×k) と比べて、大規模なデータセットでも高速に動作する点が大きな利点です。