C++で配列を毎日変換し、最終的に安定する配列を求めるアルゴリズム

初期配列 arr があるとします。毎日、前日の配列をもとに新しい配列を作成していきます。i 日目には、i-1 日目の配列に対して次の操作を施し、i 日目の配列を生成します。操作の条件は以下のとおりです。

• ある要素が、左隣と右隣の両方の値より小さい場合(谷)、その要素を 1 増やします。
• ある要素が、左隣と右隣の両方の値より大きい場合(山)、その要素を 1 減らします。
• 先頭と末尾の要素は常に変更されません。

この操作を何日か繰り返すと、配列はそれ以上変化しない安定状態に到達します。その最終的な配列を求めるのがこの問題です。たとえば、初期配列が [6,2,3,4] の場合、出力は [6,3,3,4] になります。初日に [6,2,3,4] から [6,3,3,4] へ変化した後は、それ以上の操作は行われません。

解法のアプローチ

この問題は、変化がなくなるまでシミュレーションを繰り返すことで解くことができます。具体的な手順は以下のとおりです。

1. 配列のサイズが 2 以下の場合は、変化しうる内部要素が存在しないため、そのまま配列を返します。
2. フラグ flag を true に設定します。
3. flag が true である間、次の処理を繰り返します。
   • flag を false にリセットします。
   • 空の一時配列 temp を作成し、先頭要素 arr[0] を追加します。
   • i を 1 から 配列サイズ - 2 まで順に処理します。
     • arr[i] < arr[i-1] かつ arr[i] < arr[i+1] の場合:temp に arr[i]+1 を追加し、flag を true にします。
     • arr[i] > arr[i-1] かつ arr[i] > arr[i+1] の場合:temp に arr[i]-1 を追加し、flag を true にします。
     • 上記以外の場合:arr[i] をそのまま temp に追加します。
   • 末尾要素を temp に追加します。
   • arr を temp で置き換えます。
4. ループが終了したら、arr を返します。

flag は、その日の処理で少なくとも 1 つの要素が変化したかどうかを追跡する役割を担っています。すべての要素が変化しなくなった時点でループを抜けることで、安定した最終配列が得られます。

実装例(C++)

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
#define push push_back
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> transformArray(vector<int>& arr) {
      if(arr.size()<=2)return arr;
      bool flag = true;
      while(flag){
         flag = false;
         vector <int> temp;
         temp.push_back(arr[0]);
         for(int i = 1; i < arr.size()-1; i++){
            if(arr[i]< arr[i-1] && arr[i]<arr[i+1]){
               temp.push(arr[i]+1);
               flag = true;
            }
            else if(arr[i]> arr[i-1] && arr[i]>arr[i+1]){
               flag = true;
               temp.push(arr[i]-1);
            }
            else temp.push(arr[i]);
         }
         temp.push_back(arr[arr.size()-1]);
         arr = temp;
      }
      return arr;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,6,3,4,3,5};
   print_vector(ob.transformArray(v));
}

入力

[1,6,3,4,3,5]

出力

[1,4,4,4,4,5]

この例では、初期配列 [1,6,3,4,3,5] に対して変換操作を繰り返し適用すると、最終的に [1,4,4,4,4,5] という安定した配列へと収束することが確認できます。