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

次に小さい要素とは？

「次に小さい要素（Next Smaller Element）」とは、ある要素よりも後ろに位置する要素の中で、最初に現れる「より小さい値」のことです。具体例を見てみましょう。

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

この配列では、5 の次に小さい要素は 4 です。一方、1・2・3 の後ろにはそれらより小さい要素が存在しないため、答えは -1 になります。

アルゴリズム

この問題はスタックを活用することで効率的に解けます。手順は以下の通りです。

• 配列をランダムな数値で初期化します。
• スタックを初期化し、最初の要素をプッシュします。
• 配列の各要素を順に走査します。
  • スタックが空の場合は、現在の要素をスタックにプッシュします。
  • 現在の要素がスタックの先頭（トップ）の要素より小さい間、次の処理を繰り返します。
    • 先頭の要素と、その次に小さい要素（＝現在の要素）を出力します。
    • 先頭の要素をポップします。
  • 現在の要素をスタックにプッシュします。
• 最後に、スタックが空になるまで残りの要素を取り出しながら、「次に小さい要素は -1」として出力します。

C++での実装

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

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

void nextSmallerElements(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[] = { 5, 4, 3, 2, 1 };
    int n = 5;
    nextSmallerElements(arr, n);
    return 0;
}

実行結果

上記のコードを実行すると、入力配列 {5, 4, 3, 2, 1} に対して次のような結果が出力されます。降順に並んだ配列では、各要素の直後の要素がそのまま「次に小さい要素」になります。

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

計算量

このアルゴリズムでは、各要素は最大でも1回プッシュされ、1回ポップされるだけです。そのため、時間計算量は O(n)、スタックに必要な空間計算量も最悪ケースで O(n) となります。すべての組み合わせを素朴に比較するO(n²)の手法と比べて、大幅に効率的である点が大きなメリットです。