Find the Largest Number
你会得到一个非空整数列表 nums。返回其中最大的值。这些值可能是负数，所以答案也可能是负数。请用自己的比较来找出它，不要使用像 max 这样的内置最大值函数。
函数
- numsinteger-array
- 要搜索的整数列表
- 返回值integer
- nums 中的最大值
约束条件
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
示例
- 输入
- nums = [3, 17, 4, 12, 9]
- 输出
- 17
- 解释
- 从左边开始读，目前最大的值是
3，然后是17。4、12和9都没有超过17。
- 输入
- nums = [-8, -3, -11, -3]
- 输出
- -3
- 解释
- 每个值都是负数，
-3离零最近，因此它是最大的值。它出现了两次，但你要返回的是值，而不是位置。
- 输入
- nums = [42]
- 输出
- 42
- 解释
- 只有一个值的列表中，这个值就是最大值。
进阶
你能先成对比较这些值，用大约 3n/2 次比较找出最大值和最小值，而不是用 2n 次吗？
提示
逐个打开提示，每个都会多透露一点。
一次读取一个值。对于已经看到的值，你需要记住什么？
只记住目前为止最大的值。每个新值要么比它大，要么不比它大。
将运行中的最大值设为
nums[0]，而不是0，因为每个值都可能是负数。将它与每个值进行比较，并保留较大的那个。
题解
你跳过的任何值都可能是最大的，因此每个答案都会读取每个元素。只需遍历一次并持续记录最大值，不做其他操作。将最大值设为第一个元素，绝不要设为 0，因为所有值都可能是负数。
对副本排序并取最后一个值
思路
复制 nums，这样调用者的列表就能保持原样。将副本从小到大排序，并返回最后一个元素。对于 [3, 17, 4, 12, 9]，排序后的副本是 [3, 4, 9, 12, 17]。
如果你只想取出最大的值，排序会让所有值都按顺序排列。这需要大约 n log n 次比较，当 n = 5000 时约为 60,000 次，此外还需要 O(n) 的内存来存储副本。
算法
- 复制
nums。 - 将副本按从小到大的顺序排序，并将数字作为数字进行比较。
- 返回排序后副本中的最后一个元素。
def findMax(nums):
ordered = sorted(nums) # a sorted copy, smallest first
return ordered[-1]单次遍历并维护最大值
思路
保留 largest，用来存储目前见过的最大值，并在遇到更大的值时替换它。循环结束后，它已经和每个元素都比较过了，因此列表中没有任何值比它大。对于 [3, 17, 4, 12, 9]，它从 3 开始，变成 17 后就保持不变：进行 n-1 次比较，并额外使用一个变量。
从 nums[0] 开始，才能正确处理全是负数的列表。如果从 0 开始，那么 [-8, -3, -11, -3] 中没有任何值比它大，因此你会返回 0，但这个值并不在列表中。
算法
- 将
largest设为nums[0]。 - 遍历
nums中的每个值x。 - 如果
x > largest，就将largest设为x。 - 循环结束后，返回
largest。
def findMax(nums):
largest = nums[0] # never 0: every value may be negative
for x in nums:
if x > largest:
largest = x
return largest
易错点和边界情况
- 从一个猜测的小数开始，例如
-1000000。值会降到-10^9，所以[-2000000]会返回这个猜测值。nums[0]不需要猜测。 - 在 Lua 或 R 中读取
nums[0]，这两种语言的第一个元素都是nums[1]。Lua 会返回nil，R 会返回一个空向量。 - 在基于 0 的索引中使用
i ≤ n循环，这会读取末尾之后的一个元素。 - 在 JavaScript 或 TypeScript 中排序时没有使用数值比较器。
[3, 17, 4, 12, 9]的文本顺序以9结尾，所以你会返回9。
常见问题3
在数组中查找最大值的时间复杂度是多少？
一次遍历需要 O(n) 时间和 O(1) 额外空间。对于未排序的数组，没有更快的方法，因为任何你没有读取的元素都可能是最大的。先排序需要 O(n log n)。
不使用 max，如何找出数组中的最大值？
将第一个元素存入一个变量。遍历其余元素，每当遇到更大的元素时，就将其存入变量。循环结束时，变量中保存的就是最大值。
什么时候排序是查找最大值的好方法？
当你需要的不只是最大值，比如最大的 3 个值或中位数，并且会反复询问同一个列表的这类问题时。如果只需要最大值，遍历一次更快，也不会改变列表。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def findMax(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [3, 17, 4, 12, 9]
预期输出
17