C++で配列の各要素を右側の最大値に置き換える方法

配列 A が与えられたとします。この問題では、各要素を「その要素より右側にある要素の中で最大のもの」に置き換え、最後の要素は -1 に置き換える必要があります。

例えば、A = [5, 17, 40, 6, 3, 8, 2] の場合、結果は [40, 40, 8, 8, 8, 2, -1] となります。

解法のアプローチ

この問題は、配列を右から左へ走査することで、時間計算量 O(n)・空間計算量 O(1) という非常に効率的な形で解くことができます。手順は以下の通りです。

• 配列の要素を右から左へ順に読み取ります。
• 変数 e を -1 で初期化します（これは「右側の最大値」を保持する変数です）。
• i = n - 1 から 0 までループを回します。
  • temp := e（現在の右側最大値を一時保存）
  • e := max(e, array[i])（右側最大値を更新）
  • array[i] := temp（現在の要素を右側最大値で置き換え）
• 処理後の配列を返します。

この方法なら、各位置について右側の最大値を毎回再計算する必要がなく、一度の走査で完結します。素朴な二重ループによる O(n²) の解法と比べて大幅に高速です。

実装例

以下にC++での実装例を示します。

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v){
    cout << "[";
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
    public:
        vector<int> replaceElements(vector<int>& arr) {
            int rep = -1;
            int n = arr.size();
            for(int i = n - 1; i >= 0; i--){
                int temp = rep;
                rep = max(rep, arr[i]);
                arr[i] = temp;
            }
            return arr;
        }
};

main(){
    Solution ob;
    vector<int> c = {5, 17, 40, 6, 3, 8, 2};
    print_vector(ob.replaceElements(c));
}

入力

[5, 17, 40, 6, 3, 8, 2]

出力

[40, 40, 8, 8, 8, 2, -1]

まとめ

このアルゴリズムのポイントは、右から左へ走査しながら「それまで見た最大値」を1つの変数で管理することです。これにより余分なメモリを使わず、線形時間で問題を解決できます。配列の操作系の問題では頻出のテクニックなので、ぜひ覚えておきましょう。