C++で「次の大きい要素」を求める方法：スタックを使った効率的なアルゴリズム

「次の大きい要素（Next Greater Element）」とは、配列内のある要素に対して、その後ろに最初に現れるより大きい要素のことです。具体例を見てみましょう。

arr = [4, 5, 3, 2, 1]

この場合、4 の次の大きい要素は 5 です。一方、3、2、1 については、後ろにより大きい要素が存在しないため、次の大きい要素は -1 となります。

アルゴリズム

• 配列をランダムな数値で初期化します。

• スタックを初期化します。

• 配列の最初の要素をスタックにプッシュします。

• 配列の残りの要素を先頭から順に走査します。

  • スタックが空であれば、現在の要素をスタックにプッシュして次へ進みます。

  • 現在の要素がスタックのトップ要素より大きい間、以下を繰り返します。

    • トップ要素と、その次の大きい要素である現在の要素を出力します。

    • トップ要素をポップします。

  • 現在の要素をスタックにプッシュします。

• 最後に、スタックが空になるまで以下を繰り返します。

  • 残っている要素を、次の大きい要素 -1 として出力します。

実装

以下は、上記アルゴリズムを C++ で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
void nextGreaterElements(int arr[], int n) {
    stack<int> s;
    s.push(arr[0]);
    for (int i = 1; i < n; i++) {
        if (s.empty()) {
            s.push(arr[i]);
            continue;
        }
        while (!s.empty() && s.top() < arr[i]) {
            cout << s.top() << " -> " << arr[i] << endl;
            s.pop();
        }
        s.push(arr[i]);
    }
    while (!s.empty()) {
        cout << s.top() << " -> " << -1 << endl;
        s.pop();
    }
}
int main() {
    int arr[] = { 1, 2, 3, 4, 5 };
    int n = 5;
    nextGreaterElements(arr, n);
    return 0;
}

出力結果

上記のコードを実行すると、次のような結果が出力されます。

1 -> 2
2 -> 3
3 -> 4
4 -> 5
5 -> -1

このアルゴリズムでは、各要素は最大でも一度しかプッシュ・ポップされないため、時間計算量は O(n) となり、全要素同士を比較する素朴な方法（O(n²)）に比べて非常に効率的です。スタックを活用することで、配列の「次の大きい要素」問題を線形時間で解くことができます。