C++で配列内の各要素より大きい直近の値を効率的に検索する方法

この記事では、配列内のすべての要素について、それより大きい値の中で最も近いもの（次に大きい要素）を検索する方法を解説します。要素 x より大きい値が配列内に存在する場合はその値を出力し、存在しない場合は -1 を返します。

例として、配列が [10, 5, 11, 6, 20, 12] の場合を考えてみましょう。このとき、各要素に対する次に大きい値は [11, 6, 12, 10, -1, 20] となります。最大値である 20 より大きい要素は配列内に存在しないため、-1 を出力します。

解決のアプローチ

この問題を解くには、C++ STL の set（セット）を利用します。set は二分探索木（バランス木）をベースに実装されており、常に要素がソートされた状態で保持されます。二分探索木では中順走査（in-order traversal）における後続ノードが「次に大きい要素」に相当するため、upper_bound() 関数を使えば O(log n) の計算量で目的の要素を取得できます。

アルゴリズムの手順

1. 配列のすべての要素を set に挿入します。
2. 各要素に対して upper_bound(arr[i]) を呼び出し、その要素より大きい最小の要素を取得します。
3. イテレータが end() を指す場合（より大きい要素が存在しない場合）は -1 を出力し、それ以外はイテレータが指す値を出力します。

C++での実装例

#include<iostream>
#include<set>
using namespace std;

void nearestGreatest(int arr[], int n) {
    set<int> tempSet;

    // すべての要素をsetに挿入
    for (int i = 0; i < n; i++)
        tempSet.insert(arr[i]);

    // 各要素より大きい直近の値を検索して出力
    for (int i = 0; i < n; i++) {
        auto next_greater = tempSet.upper_bound(arr[i]);
        if (next_greater == tempSet.end())
            cout << -1 << " ";
        else
            cout << *next_greater << " ";
    }
}

int main() {
    int arr[] = {10, 5, 11, 6, 20, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    nearestGreatest(arr, n);
}

実行結果

11 6 12 10 -1 20

計算量について

このアルゴリズムの時間計算量は、set への挿入と upper_bound の検索がそれぞれ O(log n) であり、これを n 個の要素に対して行うため、全体で O(n log n) となります。単純な全要素比較による O(n²) のアプローチと比べて大幅に高速化できる点が大きなメリットです。また、空間計算量は set の分だけ余分に必要となるため O(n) です。