好资源导航 » 文章资讯 » C++ 中的下一个更大的元素

C++ 中的下一个更大的元素

2023-06-07 14:38:03 82

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

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

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

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

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

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

用随机数初始化数组。

初始化一个堆栈。

将第一个元素添加到堆栈中。

遍历数组的元素。

以下一个更大的元素作为当前元素打印顶部元素。

弹出顶部元素。

如果堆栈为空，则将当前元素添加到堆栈中。

而当前元素大于栈顶元素。

将元素添加到堆栈中。

虽然堆栈不为空。

将具有下一个更大元素的元素打印为-1。

示例

让我们看看代码。

#include 
using namespace std;
void nextGreaterElements(int arr[], int n) {
   stack 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 &l " << -1 << endl;
      s.pop();
   }
}
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

结论

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

返回顶部
514930285
czq8825@qq.com

C++ 中的下一个更大的元素

示例

结论

热门推荐

随机推荐