C++の次の小さな要素

次に小さい要素は、その次の最初の小さい要素である要素です。例を見てみましょう。

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

5の次に小さい要素は4であり、要素1、2、3の次に小さい要素は-1です。これは、それらの後に小さい要素がないためです。

アルゴリズム

• 乱数で配列を初期化します

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

• スタックに最初の要素を追加します。

• 配列の要素を繰り返し処理します。

  • スタックが空の場合は、現在の要素をスタックに追加します。

  • 現在の要素はスタックの一番上の要素よりも小さいですが。

    • 一番上の要素を、次に小さい要素を現在の要素として印刷します。

    • 一番上の要素をポップします。

  • 要素をスタックに追加します。

• スタックが空ではない間。

  • 次に小さい要素を-1として要素を印刷します。

実装

以下は、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;
}

出力

上記のコードを実行すると、次の結果が得られます。

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