C++の以前のより大きな要素

この問題では、配列が与えられます。私たちのタスクは、配列内の現在の要素の前にある最大の要素を返すことです。それ以外の場合は-1を出力します。

問題を理解するために例を見てみましょう

Input: {6, 2, 7, 1, 5, 3}
Output: -1, 6, -1, 7, 7, 7

この問題を解決するための簡単で明白な解決策は、配列の前の部分のより大きな要素をチェックするネストされたループを使用することです。

ソリューションの実装を示すプログラム

例

#include <iostream>
using namespace std;
void preceddingGreatestElement(int arr[], int n){
   cout << "-1\t";
   int i, j;
   for (i = 1; i < n; i++) {
      for (j = i-1; j >= 0; j--) {
         if (arr[i]<arr[j]) {
            cout<<arr[j]<< "\t";
            break;
         }
      }
      if (j == -1)
      cout << "-1\t";
   }
}
int main() {
   int arr[] = { 6, 2, 7, 1, 12, 5 };
   int n = sizeof(arr) / sizeof(arr[0]);
   preceddingGreatestElement(arr, n);
   return 0;
}

出力

-1   6   -1   7   -1   12

この問題を解決するためのより効果的な解決策は、スタックデータ構造を使用することです。そして、スタックの一番上にある前の大きな数字を維持します。

このソリューションの実装を示すプログラム

例

#include <bits/stdc++.h>
using namespace std;
void preceddingGreatestElement(int arr[], int n) {
   stack<int> elements;
   elements.push(arr[0]);
   cout << "-1\t";
   for (int i = 1; i < n; i++) {
      while (elements.empty() == false && elements.top() < arr[i])
      elements.pop();
      if(elements.empty())
         cout<<"-1\t";
      else
         cout<<elements.top()<<"\t";
      elements.push(arr[i]);
   }
}
int main() {
   int arr[] = { 6, 2, 7, 1, 12, 5 };
   int n = sizeof(arr) / sizeof(arr[0]);
   preceddingGreatestElement(arr, n);
   return 0;
}

出力

-1   6   -1   7   -1   12