在 Python 中查找下一个更大元素

在此问题中，我们将给定一个整数数组，我们需要找到数组中每个元素的下一个更大元素。

下一个更大元素是当前元素的右侧第一个大于当前元素的元素。对于数组中不存在更大元素的元素，我们将为这些元素返回 -1。

让我们看一些例子来理解这个问题。

输入： 数组 = [ 7, 3, 9, 12, 8 ]

输出

7 -> 9

3 -> 9

9 -> 12

12 -> -1

8 -> -1

大于 7 且在其右侧的第一个元素是 9。同样，除了 8 和 12 之外，每个元素在其右侧都存在一个更大的元素。

输入： arr = [ 19, 10, 7, 5, 13 ]

输出

19 -> -1

10 -> 13

7 -> 13

5 -> 13

13 -> -1

除了 19 之外，其他元素的更大对应元素是 13。

方法 - 1

在此方法中，我们将使用两个 for 循环来遍历数组。外层循环将遍历数组中的每个元素。内层循环将负责查找当前元素的更大元素。该循环将遍历当前元素右侧的剩余元素。如果没有更大的元素，我们将为该元素打印 -1。

我们将遵循以下步骤来解决此问题

• 我们将外层循环从索引 0 开始到最后一个元素，即 len(array) - 1。
  • 对于外层循环的每个 i 元素，将从 i + 1 开始的另一个循环运行到数组的最后一个索引。
  • 如果我们找到一个大于数组第 i 个的元素，我们将打破循环；否则，我们将打印 -1。

以下是上述方法对应的 Python 代码。

代码

输出

7 - 9
3 - 9
9 - 12
12 - -1
8 - -1

时间复杂度： 由于在此方法中使用了两个循环，因此此方法的时间复杂度为 O(N2)

空间复杂度： 由于没有创建任何额外的数据结构，因此此方法的空间复杂度为 O(1)。

方法 - 2

在此方法中，我们将使用堆栈数据结构。

在此方法中，我们将使用堆栈来存储需要查找下一个更大元素的元素。在遍历数组时，我们将一个更大的元素与堆栈的元素配对。我们将继续此过程，直到堆栈的顶部元素值小于当前元素。

我们将遵循以下步骤来使用上述方法解决问题

• 我们将首先将数组的第一个元素推入堆栈。
• 现在我们将遍历数组并将其余元素推入堆栈。此外，我们遵循以下步骤
  • 我们将当前元素标记为更大元素。
  • 如果在当前迭代中堆栈非空，我们将比较堆栈的顶部元素与更大元素。
  • 如果堆栈的顶部元素小于更大元素，我们将从堆栈中弹出顶部元素。因此，堆栈中所有弹出元素的 NGE 都更大。
  • 当我们遇到一个大于堆栈顶部元素的元素时，我们将更大的元素推入堆栈。
• 循环完成后，我们将弹出所有堆栈元素，并将 -1 作为 NGE 返回。

以下是上述方法对应的 Python 代码。

代码

输出

3 - 9
7 - 9
9 - 12
8 - -1
12 - -1

时间复杂度： 由于我们运行线性循环，因此此方法的时间复杂度为 O(N)。

空间复杂度： 我们使用了额外的空间来存储元素，即堆栈；因此，空间复杂度为 O(N)。

方法 - 3

在此新方法中，我们将使用一个映射来查找数组元素的 NGE。

该方法与我们之前看到的方法类似。此方法不同之处在于，我们将只推入和弹出堆栈中的元素一次。此外，数组将在原地修改。我们将数组的元素推入堆栈，直到找到一个大于堆栈顶部元素的元素。因此，当我们找到一个小于当前数组元素的元素时，我们将弹出堆栈的顶部元素。

当所有数组元素都已访问，并且堆栈仍然非空时，堆栈的其余元素在数组中没有 NGE。因此，我们将这些元素从堆栈中弹出，并在原始数组中将其索引处的值更改为 -1。

代码

输出

[9, 9, 12, -1, -1]

时间复杂度： 我们正在使用线性循环。因此，时间复杂度为 O(N)。

空间复杂度： 此方法的空间复杂度为 O(N)。我们使用了此空间来存储堆栈和映射。

方法 - 4

有一种更好、更优化的方法来解决这个问题。现在让我们看看那种方法。

以下是使用优化方法解决问题的步骤。

• 我们将首先初始化一个大小为 n 的数组 res，其中 n 是给定数组的长度，它将包含结果 NGE。我们将向数组中添加 -1 作为每个元素的初始 NGE。
• 我们将初始化另一个变量来存储到目前为止遇到的最大元素。此变量将是 max_so_far。此变量的初始值将是给定数组索引 -1 处的元素。
• 现在我们将开始一个从左到右遍历数组的循环。
  • 对于数组的每个 i 元素，如果后续元素，即 (i + 1)th 元素，大于数组的 i 元素，那么我们将设置 res[i] = res[i +1]。原因是 (i + 1)th 元素是 i 元素的下一个更大元素。
  • 但是，假设给定数组的 (i + 1)th 元素小于同一数组的 i 元素。在这种情况下，我们将检查数组 res 的 (i +1)th 元素是小于还是大于给定数组的 i 元素。如果 res[i +1] > array[i]，那么我们将设置 res 的 i 元素等于 res 的 (i + 1)th 元素。
  • 如果 res 的 (i + 1)th 元素小于给定数组的 i 元素，那么我们将检查直到现在看到的 are_so_far。如果此值大于 i 元素，那么我们将开始另一个循环来遍历 i 元素右侧的子数组。循环将继续，直到我们找到一个大于数组 i 元素的元素。如果我们找到这样的元素，我们将设置 res[i] 等于该元素。
  • 否则，如果 max_so_far < array[i]，那么我们将只将 res[i] 保留为 -1。
  • 我们必须不断地将 max_so_far 更新为直到 i 元素的数组的最大元素。
• 最终答案将是数组 res。

代码

输出

[9, 9, 12, -1, -1]

时间复杂度： 由于我们只遍历一次元素，因此时间复杂度为 O(N)。这是平均时间复杂度；但是，由于某些特定条件的嵌套循环，最坏情况下的时间复杂度可能为 O(N2)。

空间复杂度： 由于我们不使用任何额外空间来存储元素，因此空间复杂度是恒定的，即 O(1)。