查找每个元素的下一个更大元素

在本教程中，我们将编写 Python 程序来查找给定数组中每个元素的下一个更大元素。“下一个更大元素”是指数组中位于给定元素 x 右侧的第一个大于 x 的元素。如果 x 右侧没有更大的元素，则该元素被视为 -1。

让我们理解以下示例 -

示例

输入

arr[] = [3, 8, 4, 10, 6]

输出: 3 -> 8

8 -> 10

4 -> 10

10 -> -1

6 -> -1

解释：在此示例中，对于数组中的每个元素，我们都会找到其右侧的下一个更大的元素。输出显示了元素与其下一个更大元素的映射。元素 10 和 6 在其右侧没有任何更大的元素。

解决方案 - 1

在此方法中，我们将使用两个 for 循环，外层循环逐个遍历元素，内层循环检查外层循环所选元素第一个更大的元素。然后我们检查条件，如果找到了一个更大的元素，则打印该元素作为下一个，否则打印 -1。

让我们理解以下示例 -

示例 -

输出

11 --> 13
13 --> 21
21 --> -1
3 --> -1

解释 -

在上面的代码中，我们遵循了以下步骤：

1. 首先，我们从数组的第一个元素开始，从左到右遍历数组。
2. 对于每个元素，启动另一个循环，该循环从元素的索引 + 1 开始，一直持续到数组的末尾。
3. 在此内层循环中，检查是否存在比当前元素更大的元素。
4. 如果找到了更大的元素，则打印它并退出内层循环。
5. 如果在内层循环中没有找到更大的元素，则打印 -1，表示当前元素的右侧没有更大的元素。

时间复杂度： O(N2)

辅助空间： O(1)

解决方案 - 2：使用栈查找下一个更大元素

该概念涉及使用栈来跟踪需要查找下一个更大元素的元素。在遍历数组时，当我们遇到一个更大的元素时，我们将它与栈中的元素相关联，直到栈顶元素小于当前元素。

让我们理解以下示例 -

示例 -

输出

[5, 10, 10, -1, -1]

结论

在本教程中，我们探讨了两种查找数组中每个元素的下一个更大元素的解决方案。第一种解决方案使用了嵌套循环，时间复杂度为 O(N^2)，而第二种解决方案使用了栈，时间复杂度为 O(N)，效率更高。使用栈是解决此类问题的实用方法，可提供更高的性能。