各kサイズの連続したサブアレイの最大値を見つけるC++プログラム

n個の要素と値kを持つ配列があるとします。サイズkの隣接するサブアレイのそれぞれについて最大値を見つける必要があります。

したがって、入力がarr =[3,4,6,2,8]、k =3の場合、出力は次のようになります。サイズ3の連続するサブ配列は[3,4,6]、[4,6、 2]、[6,2,8]なので、最大要素は6、6、8です。

これを解決するには、次の手順に従います-

• サイズkの両端キューQiを1つ定義します
• iを初期化する場合：=0、i
• Qiが空ではなく、arr [i]> =arr [Qiの最後の要素]の場合、次のようにします。
  • Qiから最後の要素を削除する
• Qiの最後にiを挿入

例

理解を深めるために、次の実装を見てみましょう-

#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