C++で配列の「直前のより大きい要素」を効率的に求める方法

問題の概要

この問題では、整数の配列が与えられます。配列の各要素について、その要素より前方(左側)に位置する要素の中で最大の値を見つけて出力します。該当する要素が存在しない場合は -1 を出力します。

入出力例

入力: {6, 2, 7, 1, 5, 3}
出力: -1, 6, -1, 7, 7, 7

この例では、最初の要素「6」の前方には要素が存在しないため -1。2番目の要素「2」の前方にあるのは「6」だけなので 6。3番目の要素「7」の前方に「7」より大きい要素はないため -1。4番目の要素「1」の前方には「7」があるので 7。以降も同様に判定していきます。

解法1: 二重ループによる単純なアプローチ

最も分かりやすい方法は、ネストしたループ(二重ループ)を使うことです。外側のループで各要素を順に走査し、内側のループでその要素より前方の部分を後ろから調べ、最初に見つかったより大きい要素を出力します。

実装例

#include <iostream>
using namespace std;

void precedingGreatestElement(int arr[], int n){
    cout << "-1\t";
    int i, j;
    for (i = 1; i < n; i++) {
        for (j = i-1; j >= 0; j--) {
            if (arr[i] < arr[j]) {
                cout << arr[j] << "\t";
                break;
            }
        }
        if (j == -1)
            cout << "-1\t";
    }
}

int main() {
    int arr[] = { 6, 2, 7, 1, 12, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    precedingGreatestElement(arr, n);
    return 0;
}

出力

-1   6   -1   7   -1   12

この方法は実装がシンプルで理解しやすい反面、時間計算量が O(n²) になるため、配列のサイズが大きくなると処理速度が低下します。

解法2: スタックを使った効率的なアプローチ

より効率的な解法として、スタック(stack)データ構造を利用する方法があります。スタックのトップに常に「直前のより大きい要素」を保持しておくことで、各要素の答えを高速に取り出せます。

処理の手順は次のとおりです。

• 最初の要素をスタックにプッシュし、-1 を出力します(最初の要素の前方には何もないため)。
• 2番目以降の各要素について、スタックのトップがその要素より小さい間、ポップを繰り返します。
• スタックが空になった場合は -1 を、空でなければスタックのトップの値を出力します。
• 最後に現在の要素をスタックにプッシュして次へ進みます。

実装例

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

void precedingGreatestElement(int arr[], int n) {
    stack<int> elements;
    elements.push(arr[0]);
    cout << "-1\t";
    for (int i = 1; i < n; i++) {
        while (elements.empty() == false && elements.top() < arr[i])
            elements.pop();
        if (elements.empty())
            cout << "-1\t";
        else
            cout << elements.top() << "\t";
        elements.push(arr[i]);
    }
}

int main() {
    int arr[] = { 6, 2, 7, 1, 12, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    precedingGreatestElement(arr, n);
    return 0;
}

出力

-1   6   -1   7   -1   12

まとめ

この問題は「Previous Greater Element(直前のより大きい要素)」と呼ばれる古典的な配列操作の問題です。二重ループによる解法は O(n²)、一方スタックを使った解法は各要素が最大1回ずつプッシュ・ポップされるため O(n) の時間計算量で処理できます。大量のデータを扱う場合やパフォーマンスが重要な場面では、スタックを活用したアプローチを選ぶのが効果的です。