查找数组中的领导者

在本教程中，我们将编写 Python 代码来查找给定数组中的领导者元素。领导者是指数组中大于或等于其右侧所有元素的元素。换句话说，如果一个元素大于或等于数组中它后面的每个元素，则该元素被认为是领导者。

让我们理解以下示例 -

示例 -

解释 -

17 大于其右侧的所有元素（4、3、5、2）。

5 大于其右侧的所有元素（2）。

2 是最右边的元素，因此它始终被认为是领导者。

所以，这个数组中的领导者是 [17, 5, 2]

示例 -

解释 -

4 和 0，因为它们大于或等于其右侧的所有元素。

让我们来理解上面问题的解决方案。

解决方案

我们将使用不同的方法来解决这个问题。

朴素方法

1. 初始化一个空列表来存储领导者。
2. 开始从数组的最左侧元素迭代到倒数第二个元素（不包括最后一个元素，因为它始终是领导者）。
3. 对于索引 i 处的每个元素 A[i]
   1. 初始化一个标志变量 is_leader 为 True，假设 A[i] 最初被认为是领导者。
   2. 开始迭代 A[i] 右侧的元素，从 A[i+1] 到最后一个元素。
   3. 对于 A[i] 右侧的每个元素 A[j]
      如果 A[j] 大于或等于 A[i]，则继续检查下一个元素。
      如果 A[j] 小于 A[i]，则将 is_leader 设置为 False 并跳出循环，因为 A[i] 不能是领导者。
   4. 在检查完 A[i] 右侧的所有元素后，如果 is_leader 仍然为 True，则表示 A[i] 是领导者。将 A[i] 添加到领导者列表中。
4. 循环完成后，领导者列表将包含数组中找到的所有领导者。

让我们理解以下示例 -

示例 -

输出

Leaders in the array: [4, 0]

解释 -

我们定义一个函数 find_leaders()，它接受一个数组 arr 作为输入。

我们初始化空列表 leaders 来存储在数组中找到的领导者。

我们使用两个嵌套循环从左到右遍历数组。外层循环遍历从第一个到倒数第二个元素，内层循环将每个元素与其右侧的元素进行比较。

我们使用布尔变量 is_leader 来假设当前元素最初是一个领导者。

在内层循环中，如果我们发现任何元素大于当前元素，我们将 is_leader 设置为 False 并跳出循环，因为当前元素不能是领导者。

如果在检查完右侧所有元素后 is_leader 仍然为 true，则表示当前元素是领导者，因此我们将其添加到 leaders 列表中。

最后，我们将最右边的元素（最后一个元素）添加到 leaders 列表中，因为它始终是领导者。

查找数组中领导者的朴素方法的 time complexity 为 O(n^2)，space complexity 为 O(1)。

方法 2：通过查找后缀最大值来查找领导者

查找数组中的后缀最大值意味着识别数组中特定元素右侧（包括该元素本身）元素中的最大值。

以下是后缀最大值的方法。

首先初始化一个变量，用于在从右到左遍历数组时跟踪遇到的最大值。

开始从右到左遍历数组。

在每一步，将当前元素与迄今为止遇到的最大值（在步骤 1 中初始化）进行比较。

如果当前元素大于最大值，则将最大值更新为当前元素，因为它代表了当前元素右侧的最大值。

对数组中的所有元素重复此过程，有效地找到每个元素后缀（右侧元素）中的最大值。

在遍历数组时，记录或打印每个元素遇到的最大值。这些记录的值代表原始数组中相应元素的后缀最大值。

让我们理解以下示例 -

示例 -

输出

Leaders in the array: [17, 5, 2]

解释 -

我们定义一个函数 find_leaders，它接受一个数组 arr 作为输入。

我们找到数组的长度 n 并初始化空列表 leaders 来存储领导者元素。

我们首先将 max_right 变量初始化为数组的最右侧元素，即 arr[n - 1]。最右侧元素始终是领导者，因此我们将其添加到 leaders 列表中。

然后，我们从倒数第二个元素（索引 n - 2）到第一个元素（索引 0）以反序（从右到左）遍历数组。

在循环中，我们将每个元素与当前的 max_right 进行比较。如果当前元素大于或等于 max_right，它将成为新的领导者，并相应地更新 max_right。

我们在遇到每个领导者元素时将其添加到 leaders 列表中。

循环结束后，我们反转 leaders 列表以获得按原始顺序排列的元素。

最后，我们返回包含数组中所有领导者元素的 leaders 列表。

在示例用法中，我们使用示例数组调用 find_leaders 函数并打印找到的领导者。

方法 3：基于堆栈的方法

前面的方法提供了线性时间复杂度，但它没有按照输入数组中出现的顺序来维护元素。为了在查找领导者时保留元素的原始顺序，我们可以使用堆栈数据结构。

以下是使用基于堆栈的方法识别数组中领导者的修订步骤

1. 从数组的最后一个索引开始。最右边的元素始终是领导者，因为其右侧没有元素。
2. 继续以反序遍历数组，向索引位置 0 移动。
3. 在遍历数组时，维护一个遇到的最大值的记录。
4. 每当遇到一个大于先前记录的最大值的元素时，就将其视为领导者并将其推入堆栈。
5. 完成迭代后，遍历堆栈并打印其内容，因为这些元素代表了原始数组中的领导者。

让我们理解下面的例子。

示例 -

输出

4 0

解释 -

我们定义一个函数 find_leaders，它接受一个数组 arr 作为输入。

我们计算输入数组 n 的长度并初始化一个空堆栈 stack 来存储领导者。

我们将 max_element 初始化为输入数组的最后一个元素，因为最右边的元素始终是领导者。我们将其推入堆栈以开始。

然后，我们使用 for 循环以反序遍历数组，从倒数第二个元素（索引 n-2）到第一个元素（索引 0）。

在循环中，我们将当前元素 arr[i] 与 max_element 进行比较。如果当前元素大于或等于 max_element，则认为它是领导者，因此将其推入堆栈。如果当前元素更大，我们还将 max_element 更新为当前元素。

遍历数组后，我们已在堆栈中识别并存储了领导者。

最后，我们通过从堆栈中弹出元素并打印它们来按输入数组中的出现顺序打印领导者。

结论

在本教程中，我们学习了如何在数组中查找领导者元素，即大于或等于其右侧所有元素的元素。我们探索了三种不同的方法：朴素方法，该方法涉及遍历数组并将每个元素与其右侧的元素进行比较。其 time complexity 为 O(n^2)。通过查找后缀最大值来查找领导者，我们通过查找每个元素右侧的最大元素来优化过程。它实现了 O(n) 的线性 time complexity 并保留了元素的顺序。以及基于堆栈的方法，该方法用于维护元素的原始顺序，我们使用了堆栈。从最右边的元素开始，我们以反序遍历数组，将领导者推入堆栈。此方法也具有 O(n) 的 time complexity。