C++の配列で次の小さい方から次の大きい方を検索

この問題では、n個の整数値で構成される配列arr[]が与えられます。私たちのタスクは、配列内で次の小さいものを見つけることです。

問題の説明 −配列内の現在の要素よりも大きい要素を見つけてから、この大きい要素よりも小さい要素を配列内で見つけます。そして、配列に次に小さい要素または次に大きい要素が存在しない場合は、-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が、現在の要素の次に大きい要素のインデックスを格納することを意味します。たとえば、nextGreater [i]には、次に大きい要素のインデックスがあり、これはarr[nextGreater[i]]になります。また、nextSmaller[]についても同じことが言えます。

したがって、配列の次に大きい要素の次に小さい要素にアクセスします。 nextGreater[i]でインデックスの次に小さい要素を見つけます。これにより、必要な要素のインデックスが提供されます。つまり、必要な要素はarr [nextSmaller[nextGreater[i]]]です。

要素を見つけるために、残りのサブアレイの要素を格納するスタックデータ構造を使用します。より大きな要素を見つけるために関数がどのように機能するかを次に示します。

• =>最後のi->n-1から0まで配列をトラバースします。

• =>スタックが空ではなく、スタックの最上位がcurrentelement-> pop Sよりも小さい場合は、より大きな要素が見つかるか、スタックが空になるまでこれを実行します。

• =>スタックが空の場合->これ以上の要素はあり得ない場合は、-1、nextGreater [i]=-1を格納します。

• => else->次に大きい要素がスタックの一番上にあり、スタックの一番上を格納します。nextGreater[i] =stack.top（）。

• =>現在の要素をスタックにプッシュします。stack.push（）

同じ方法を使用して、配列の現在の要素の次に小さい要素を見つけることができます。そして、両方のインデックスを見つけたら。これらのインデックスを使用して、配列から必要な要素を見つけることができます。

ソリューションの動作を説明するプログラム

例

#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<<"All next smaller of next greater elements of the array are ";
   findNextSmallerofNextGreaterElemenetArray(arr, n);
   return 0;
}

出力

All next smaller of next greater elements of the array are 3 3 1 1 -1 -1