Second Largest Number
给定一个整数列表 nums。返回其中第二大的不同值：严格小于最大值的最大值。值可能重复，因此对于 [5, 5, 3]，答案是 3，而不是 5。列表中始终至少有两个不同的值。
函数
- numsinteger-array
- 至少包含两个不同值的整数列表
- 返回值integer
- 小于最大值的最大值
约束条件
2 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109nums中至少包含两个不同的值。
示例
- 输入
- nums = [4, 9, 2, 7, 9]
- 输出
- 7
- 解释
- 最大值是
9。它出现了两次，但最大值的第二个副本不计入，因此答案是下一个较小的值，即7。
- 输入
- nums = [-5, -1, -8]
- 输出
- -5
- 解释
- 从大到小，值依次为
-1、-5、-8，所以第二大的值是-5。
- 输入
- nums = [6, 6, 6, 3]
- 输出
- 3
- 解释
- 只有两个不同的值，
6和3。无论6重复多少次，第二大的值都是3。
进阶
你能否只遍历一次，用三个变量且不排序，返回第三大的不同值？
提示
逐个打开提示，每个都会多透露一点。
查找最大值需要一个变量。阅读列表时，第二个变量能帮你记住什么？
跟踪最大的值和第二大的不同值。新值可能超过最大值，严格落在这两个值之间，也可能不改变任何值。
将下面两个变量都初始化为小于所有允许值的值。如果
x > largest，就把largest移到second中，并存入x。否则，如果x严格大于其中较小的值且小于较大的值，就把它存入second。
题解
最大值可以重复出现，但重复值不能算作第二大值。答案可能是负数，因此，如果列表中的值全为负数，以 0 开始的变量就不适用。只需遍历一次，并通过严格比较跟踪两个不同的最大值，就能同时处理这两种情况。
排序并逐步递减，直到达到最大值
思路
先排序并复制列表，然后从末尾向左遍历，越过所有最大值；第一个不同的值就是答案。对于 [6, 6, 6, 3]，跳过三个 6，就会到达 3。遍历不会越过列表开头，因为列表中有两个不同的值。
当你只需要最大的两个值时，排序会对每个值进行排序：时间复杂度为 O(n log n)，复制列表还需要 O(n) 的内存。
算法
- 复制
nums，并将副本按从小到大的顺序排序。 - 将索引
i设为最后一个位置。 - 当
i处的值等于最大值时，将i向左移动一位。 - 返回
i处的值。
def secondLargest(nums):
ordered = sorted(nums)
i = len(ordered) - 1
# Step left past every copy of the maximum.
while ordered[i] == ordered[-1]:
i -= 1
return ordered[i]两次遍历
思路
第一遍找出最大值。第二遍保留严格小于最大值的最大值。对于 [4, 9, 2, 7, 9]，第一遍找出 9，第二遍跳过两个 9，并保留 7。
将 second 初始化为小于所有允许值的值。某个值小于最大值，因此这个初始值一定会被替换。每一遍都是在计算运行中的最大值：时间复杂度为 O(n)，空间复杂度为 O(1)。代价是需要读取列表两次，而对于只能看一次的值流，这种做法行不通。
算法
- 遍历
nums一次，并将最大值存入largest。 - 将
second设为小于所有允许值的值。 - 再次遍历。对于每个满足
x < largest且x > second的x，将second设为x。 - 返回
second。
def secondLargest(nums):
largest = nums[0]
for x in nums:
if x > largest:
largest = x
second = float("-inf") # below every allowed value
for x in nums:
if x < largest and x > second:
second = x
return second一次遍历，记录最大的两个值
思路
用 largest 和 second 保存目前最大的两个不同值。比 largest 大的值会把原来的 largest 降为 second。严格大于 second 且小于 largest 的值会替换 second。其他情况都不改变它们，包括再次出现的 largest：严格比较会跳过重复值。
对于 [4, 9, 2, 7, 9]，largest 先是 4，然后变成 9，此时 second = 4。7 位于它们之间，所以 second = 7，最后一个 9 会被跳过。将两个变量都初始化为小于所有可能值的数，因为答案可能是负数。有两个不同的值，就能保证 second 最终会是列表中的一个值。
算法
- 将
largest和second设为小于所有允许值的值。 - 遍历
nums中的每个值x。 - 如果
x > largest，就将largest移到second，并将largest设为x。 - 否则，如果
x < largest且x > second，就将second设为x。 - 循环结束后，返回
second。
def secondLargest(nums):
# Both start below every allowed value.
largest = second = float("-inf")
for x in nums:
if x > largest:
second = largest # the old maximum drops to second place
largest = x
elif largest > x > second:
second = x
return second
易错点和边界情况
- 返回排序后列表中倒数第二个元素。如果最大值重复出现，例如
[4, 9, 2, 7, 9]，那么返回的仍是最大值。 - 将变量初始值设为
0。对于[-5, -1, -8]，没有任何值大于0，因此你会返回0，但它不在列表中。 - 在第一种情况下写
x >= largest。第二个9会将第一个9放入second，然后你会返回9。 - 只在出现新的最大值时更新
second。在[10, 20, 15]中，15始终不会进入second，因此你会返回10。
常见问题3
查找第二大元素的时间复杂度是多少？
单趟和两趟方法都需要 O(n) 时间和 O(1) 额外空间；先排序需要 O(n log n) 时间。你无法优于 O(n)，因为每个值都必须读取一次。
重复项会如何影响第二大的元素？
这道题要求找出第二大的不同值，因此会跳过最大值的重复项：[9, 9, 7] 的答案是 7。有些版本按位置计数，答案会是 9，所以编写代码前要先确认题目要求的是哪一种。
没有第二大的值时，你应该返回什么？
这里不会发生这种情况，因为列表中包含两个不同的值。一般来说，像 [4, 4, 4] 这样的列表没有答案：返回一个标记，例如 -1 或 null，或者引发错误。循环结束后，如果 second 仍然是初始值，你就能发现这种情况。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def secondLargest(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [4, 9, 2, 7, 9]
预期输出
7