C++で配列内の「次に大きい要素の次に小さい要素」を効率的に検索する方法

問題の概要

この問題では、n個の整数で構成される配列 arr[] が与えられます。各要素について、まず配列内でその要素より大きい「次に大きい要素（Next Greater）」を見つけ、続いてその大きい要素に対してさらに小さい「次に小さい要素（Next Smaller）」を求めるのがタスクです。

もし次に大きい要素、あるいはその次に小さい要素が配列内に存在しない場合は、-1 を返します。

入力例と出力例

入力

arr[] = {4, 2, 8, 3, 9, 1}

出力

{3, 3, 1, 1, -1, -1}

説明

まず各要素の「次に大きい要素」の配列を作ると {8, 8, 9, 9, -1, -1} となります。9 は配列の最大値、1 は最後の要素であるため、これらには次に大きい要素が存在しません。

次に、それぞれの「次に大きい要素」に対する「次に小さい要素」を求めると、結果は {3, 3, 1, 1, -1, -1} になります。

解法アプローチ①：素朴な方法（ブルートフォース）

最もシンプルな解法は、配列を反復処理し、各要素ごとに以下の手順を実行することです。

• 配列の中から現在の要素より大きい「次に大きい要素」を探す。

• その大きい要素以降の残りの配列から、それより小さい要素を探す。

この方法でも目的は達成できますが、二重ループが必要となるため、時間計算量は O(n²) となり、大きな配列では非効率です。

解法アプローチ②：スタックを使った効率的な方法

より優れた解法として、スタックと要素のインデックスを活用する方法があります。

ここでは、nextGreater[] と nextSmaller[] という2つの配列を用意し、現在の要素の「次に大きい要素」「次に小さい要素」のインデックスをそれぞれ格納します。たとえば nextGreater[i] には、arr[nextGreater[i]] が arr[i] の次に大きい要素となるようなインデックスが保存されます。nextSmaller[] も同様です。

こうすることで、「次に大きい要素の次に小さい要素」は、nextGreater[i] の位置にある要素の次に小さい要素を調べることで取得できます。つまり、求める要素は arr[nextSmaller[nextGreater[i]]] となります。

スタックによる「次に大きい要素」の探索手順

• 配列を末尾から先頭へ向かって走査します（i = n-1 から 0 へ）。

• スタックが空でなく、スタックのトップが現在の要素以下である間、スタックからポップを繰り返します。より大きい要素が見つかるか、スタックが空になるまで続けます。

• スタックが空になった場合 → 次に大きい要素は存在しないため、nextGreater[i] = -1 を格納します。

• それ以外の場合 → 次に大きい要素はスタックのトップにあるため、nextGreater[i] = stack.top() を格納します。

• 最後に現在の要素のインデックスをスタックにプッシュします。

比較条件を逆にすれば、同じ手法で「次に小さい要素」も求められます。両方のインデックス配列が完成すれば、それらを組み合わせて目的の要素を O(1) で参照できます。全体の時間計算量は O(n) に抑えられます。

C++での実装例

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

// 各要素の「次に大きい要素」のインデックスを求める
void findNextGreater(int arr[], int n, int next[]) {
   stack<int> nextGreater;
   int i = n-1;
   while(i >= 0) {
      while (!nextGreater.empty() && arr[nextGreater.top()] <= arr[i])
         nextGreater.pop();
      if (!nextGreater.empty())
         next[i] = nextGreater.top();
      else
         next[i] = -1;
      nextGreater.push(i);
      i--;
   }
}

// 各要素の「次に小さい要素」のインデックスを求める
void findNextSmaller(int arr[], int n, int next[]) {
   stack<int> nextSmaller;
   int i = n-1;
   while(i >= 0){
      while (!nextSmaller.empty() && arr[nextSmaller.top()] >= arr[i])
         nextSmaller.pop();
      if (!nextSmaller.empty())
         next[i] = nextSmaller.top();
      else
         next[i] = -1;
      nextSmaller.push(i);
      i--;
   }
}

// 「次に大きい要素の次に小さい要素」を出力する
void findNextSmallerofNextGreaterElemenetArray(int arr[], int n) {
   int nextGreaterIndex[n];
   int nextSmallerIndex[n];
   findNextGreater(arr, n, nextGreaterIndex);
   findNextSmaller(arr, n, nextSmallerIndex);
   for (int i=0; i<n; i++){
      if (nextGreaterIndex[i] != -1 && nextSmallerIndex[nextGreaterIndex[i]] != -1)
         cout<<arr[nextSmallerIndex[nextGreaterIndex[i]]]<<"\t";
      else
         cout<<"-1"<<"\t";
   }
}

int main(){
   int arr[] = {4, 2, 8, 3, 9, 1};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"配列の各要素における「次に大きい要素の次に小さい要素」は ";
   findNextSmallerofNextGreaterElemenetArray(arr, n);
   return 0;
}

実行結果

配列の各要素における「次に大きい要素の次に小さい要素」は 3 3 1 1 -1 -1

まとめ

スタックとインデックス管理を組み合わせることで、一見 O(n²) かかりそうな問題を O(n) の線形時間で解くことができます。「次に大きい要素」「次に小さい要素」を求めるスタックベースのテクニックは、配列に関する多くの応用問題で役立つ重要なパターンなので、ぜひマスターしておきましょう。