Leaders in an Array
给你一个整数数组 nums。如果一个元素大于或等于它右侧的所有元素，它就是一个领导元素。最后一个元素右侧没有元素，所以它始终是领导元素。按领导元素在 nums 中从左到右出现的顺序，返回所有领导元素。
函数
- numsinteger-array
- 要搜索的整数数组
- 返回值integer-array
- nums 的前导元素，从左到右
约束条件
1 ≤ nums.length ≤ 25000-109 ≤ nums[i] ≤ 109
示例
- 输入
- nums = [12, 5, 9, 3, 6, 2]
- 输出
- [12, 9, 6, 2]
- 解释
- 2 排在最后，所以它先移动。6 大于它后面的 2，9 大于 3、6 和 2，12 大于所有数字。5 不如 9，3 不如 6，所以答案是
[12, 9, 6, 2]。
- 输入
- nums = [4, 7, 7, 1, 7]
- 输出
- [7, 7, 7]
- 解释
- 计数规则：索引 1 和 2 处的 7 右侧只有一个相等的 7，所以它们都和最后一个 7 并列领先。4 和 1 的右侧各有一个 7。
- 输入
- nums = [-3]
- 输出
- [-3]
- 解释
- 单个元素就是最后一个元素，所以它是最大的元素，无论它是负数还是正数。
进阶
如果值是逐个到达的，并且每次到达后都必须报告目前的领先者，那么怎样才能做到每个值的摊销更新时间为 O(1)？
提示
逐个打开提示，每个都会多透露一点。
要判断
nums[i]是否是领导者，只需要知道右侧部分的一个数字。是哪一个？当一个元素大于或等于其右侧所有元素的最大值时，它就是领袖。从右端开始遍历时，你可以一路更新这个最大值。
从最后一个元素开始，将它同时作为找到的第一个领袖和当前最大值。向左移动：每个大于或等于当前最大值的值都是领袖，并成为新的最大值。你会从右向左收集领袖，因此返回前要将它们反转。
题解
从左向右读取时，每个元素都需要重新扫描它后面的部分。改为从右向左遍历：你只需要知道后缀中的最大值，用一个变量就能保存它。这样就能把 O(n²) 的检查变成一次遍历。
检查右侧的所有内容
结果正确，但无法在最大的测试中运行完毕
思路
应用定义：对于每个索引 i，扫描后面的元素，并在遇到第一个严格大于 nums[i] 的元素时停止。如果扫描到末尾，nums[i] 就是领袖。你从左到右检查索引，因此领袖会按顺序出现。在 [12, 5, 9, 3, 6, 2] 中，5 遇到 9 时停止，3 遇到 6 时停止。
开销在于那些一直扫描到末尾的过程。如果 24,999 个相等的值后面跟着一个更大的值，那么每个元素几乎都要遍历整个数组：约为 25,000 × 25,000 / 2，也就是超过 3 × 10^8 次比较。
算法
- 创建一个空的结果列表。
- 对于每个索引
i，从i + 1开始扫描j，直到末尾。 - 如果某个
nums[j]大于nums[i]，就停止：nums[i]不是一个领袖。 - 如果不存在这样的
j，就将nums[i]添加到结果中。 - 返回结果。
def leaders(nums):
n = len(nums)
result = []
for i in range(n):
is_leader = True
for j in range(i + 1, n):
if nums[j] > nums[i]: # a bigger value on the right rules it out
is_leader = False
break
if is_leader:
result.append(nums[i])
return result从右侧开始的一次遍历，并维护最大值
思路
每个元素都至少和右侧所有元素一样大，这等同于它至少和右侧元素的最大值一样大。从右向左遍历时，你可以持续更新这个最大值。最后一个元素是最右侧的元素，因此它是第一个领队元素，也作为初始最大值。它左侧的每个元素如果至少和当前最大值一样大，就是领队元素，并成为新的最大值；否则，说明它右侧有更大的值。
对于 [12, 5, 9, 3, 6, 2]：2 是领队元素，接着是 6、9、12，而 3 和 5 都小于最大值。你找到了 [2, 6, 9, 12]；将其反转后，就是答案。
每个元素只比较一次：时间复杂度为 O(n)，除结果外的额外空间复杂度为 O(1)。R 版本会在一个 logical(n) 向量中标记领队元素，因此额外空间复杂度为 O(n)。
算法
- 将最后一个元素放入 result，并将
best设为它。 - 将
i从倒数第二个索引递减到 0。 - 如果
nums[i] ≥ best，就将nums[i]添加到 result，并将best设为它。 - 反转 result，让 leaders 从左到右排列，然后返回它。
def leaders(nums):
n = len(nums)
best = nums[n - 1] # the largest value to the right of the current index
found = [best] # the last element is always a leader
for i in range(n - 2, -1, -1):
if nums[i] >= best:
best = nums[i]
found.append(nums[i])
found.reverse() # collected right to left, returned left to right
return found
易错点和边界情况
- 将
>用作与当前最大值比较的运算符，而不是≥。在[4, 7, 7, 1, 7]中，每个 7 都是领先元素，但严格比较只会保留最后一个。 - 将最大值设为 0，而不是最后一个元素。
[-1, -5]必须同时返回这两个元素，但最大值为 0 会将它们排除。 - 按找到的顺序返回领先元素，例如返回
[2, 6, 9, 12]，而不是[12, 9, 6, 2]。 - 已经将最后一个元素放入结果后，又从最后一个索引开始循环，导致最后一个元素被添加两次。
- 只将每个元素与相邻元素比较。在
[5, 3, 9]中，5 虽然比旁边的 3 大，但 9 的存在意味着答案是[9]。
常见问题3
在数组中查找主导元素的时间复杂度是多少？
从右侧遍历一次的时间复杂度是 O(n)，因为每个元素只会与当前最大值比较一次。如果将每个元素都与它右侧的所有元素进行比较，最坏情况下的时间复杂度为 O(n²)，例如所有值都相等时。
最后一个元素总是领导者吗？
是的。一个领导元素必须大于或等于它右侧的每个元素，而最后一个元素右侧没有元素，因此无需检查任何内容，条件也成立。
相等的值也算领先者吗？
这里是的：一个领袖必须大于或等于右侧的每个元素，所以在 [4, 7, 7, 1, 7] 中，3 个 7 都是领袖。有些版本要求严格大于，这时要用 > 比较，并且只有并列值中最后一个才是领袖。
def leaders(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [12, 5, 9, 3, 6, 2]
预期输出
[12, 9, 6, 2]