与 C++ 中的输入顺序相同的下一个更大的元素

在本教程中，我们将编写一个程序，为数组中的所有元素查找下一个更大的元素。

下一个更大的元素是它之后的第一个更大的元素。让我们看一个例子。

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

4 的下一个更大的元素是 5，元素 3、2、1 的下一个更大的元素是 -1，因为它们之后没有更大的元素。

我们可以在O(n)时间复杂度上使用堆栈来解决问题。

让我们看看解决问题的步骤。

• 用随机数初始化数组。

• 初始化一个栈和一个数组。

• 从数组的末尾开始迭代。

• 从栈中移除元素，直到栈为空且栈顶元素小于或等于当前元素。

• 如果堆栈为空，则没有下一个更大的元素。所以将 -1 添加到结果数组中。

• 如果堆栈不为空，则顶部元素是当前元素的下一个更大的元素。将其添加到结果数组中。

• 将当前元素压入堆栈。

• 迭代结果数组并打印每个元素及其下一个更大的元素。

示例

让我们看看代码。

#include <bits/stdc++.h>
using namespace std;
void nextGreaterElements(int arr[], int n) {
   stack<int> s;
   int result[n];
   for (int i = n - 1; i >= 0; i--) {
      while (!s.empty() && s.top() <= arr[i]) {
         s.pop();
      }
      if (s.empty()) {
         result[i] = -1;
      }else {
         result[i] = s.top();
      }
      s.push(arr[i]);
   }
   for (int i = 0; i < n; i++) {
      cout << arr[i] << " -> " << result[i] << endl;
   }
}
int main() {
   int arr[] = { 1, 2, 3, 4, 5 };
   int n = 5;
   nextGreaterElements(arr, n);
   return 0;
}

如果你运行上面的代码，那么你会得到下面的结果。

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

结论

如果您对本教程有任何疑问，请在评论部分提及。