Find Peak Element
数组 nums 先递增再递减：直到某个索引为止，每个值都大于前一个值；该索引之后的每个值都小于前一个值。任一部分都可以为空，因此数组可能只递增或只递减。转折索引处的值就是峰值，它是唯一一个大于其所有相邻值的值。
请在 O(log n) 时间内返回峰值的索引。
函数
- numsinteger-array
- 这些值先逐渐增大，达到一个峰值后再逐渐减小。
- 返回值integer
- 峰值的索引
约束条件
1 ≤ nums.length ≤ 5000-106 ≤ nums[i] ≤ 106nums[i] != nums[i+1]对每个有效的i都成立。nums严格递增到某个索引为止，之后严格递减，因此恰好有一个峰值。
示例
- 输入
- nums = [2, 5, 9, 4, 1]
- 输出
- 2
- 解释
- 这些值依次升到 2、5 和 9，然后降到 4 和 1。转折点是 9，索引为 2。
- 输入
- nums = [8, 6, 3, -2]
- 输出
- 0
- 解释
- 数组只会下降，因此上升的部分为空，峰值是第一个值，即索引 0 处的 8。
- 输入
- nums = [-7, -3, 0, 12, 40]
- 输出
- 4
- 解释
- 数组只会递增，所以峰值是最后一个值，索引 4 处的 40。负值不会改变任何内容。
进阶
在一个任意两个相邻单元格都不相等的网格中，峰值是一个大于最多四个相邻单元格的单元格。你能不能不读取每个单元格就找到一个峰值？
提示
逐个打开提示，每个都会多透露一点。
任选一个索引
mid，然后查看nums[mid+1]。这一步的方向能告诉你峰值在哪里？上升只会发生在峰值之前，下降只会发生在峰值处或之后。因此，一次比较就能排除
mid的一侧。维护一个始终包含峰值的范围。向上移动时，将
lo移到mid+1；否则将hi移到mid。当它们相遇时停止。
题解
只有一个峰值时，峰值就是最大值，因此遍历一遍就能在 O(n) 时间内找到它。要达到 O(log n)，比较 nums[mid] 和 nums[mid+1]：mid 处的斜率会告诉你它位于峰值的哪一侧，因此每一步都可以排除一半的范围。
一直走，直到数值开始下降
思路
在峰值之前，每个值都小于下一个值；从峰值开始，每个值都大于下一个值。因此，峰值是第一个满足 i 处的 nums[i] > nums[i+1] 的索引；如果数组一直递增，峰值就是最后一个索引。
当峰值位于包含 5000 个值的数组末尾时，遍历需要进行 4999 次比较，而二分查找只需要 13 次。
算法
- 对于从 0 到
n-2的i，比较nums[i]和nums[i+1]。 - 在第一个
nums[i]较大的i处，返回i。 - 如果循环结束时没有出现下降，则返回
n-1。
def findPeakElement(nums):
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
return i # the first step down starts at the peak
return len(nums) - 1 # never went down: the last value is the peak斜率上的二分查找
思路
读取一对值：nums[mid] 和 nums[mid+1]。向上的一步表示数组仍在上升，在这个数组中，这只会发生在峰值之前：峰值位于 mid+1 或其右侧。向下的一步表示你已经到达峰值或越过了峰值：峰值位于 mid 或其左侧。
维护一个始终包含峰值的范围 [lo, hi]。向上的一步会将 lo 移到 mid+1。向下的一步会将 hi 移到 mid，保留 mid，因为它可能就是峰值。当 lo 与 hi 相等时，剩下的那个索引就是峰值。将 mid 向下取整可以使它小于 hi，因此 mid+1 总是存在。
在第一个示例中，mid = 2 时看到 9 > 4，因此 hi = 2；接着 mid = 1 时看到 5 < 9，因此 lo = 2，也就是峰值。5000 个值最多需要 13 步。
算法
- 将
lo = 0和hi = n-1设为初始值。 - 当
lo < hi时，取mid = lo + (hi - lo) / 2，并向下取整。 - 如果
nums[mid] < nums[mid+1]，则设置lo = mid + 1。 - 否则，设置
hi = mid。 - 返回
lo。
def findPeakElement(nums):
lo, hi = 0, len(nums) - 1 # the peak is always inside [lo, hi]
while lo < hi:
mid = lo + (hi - lo) // 2 # mid < hi, so mid + 1 is a valid index
if nums[mid] < nums[mid + 1]:
lo = mid + 1 # still climbing: the peak is to the right of mid
else:
hi = mid # going down: the peak is mid or to its left
return lo
易错点和边界情况
- 在步骤递减时设置
hi = mid - 1。在[2, 5, 9, 4, 1]中，第一个mid就是峰值本身，而hi = 1会将它排除，搜索结果会返回 1。 - 将
mid向下取整时，使用nums[mid-1]进行比较。mid可能为 0，此时左侧没有相邻元素。 - 使用左闭右开的范围并设置
hi = n。这样mid可能为n-1，此时读取nums[mid+1]会越界，即使只有一个值也会发生这种情况。 - 忘记在 Lua 和 R 中进行偏移。答案仍然是从 0 开始的索引，因此位置
i要以i-1的形式返回。
常见问题3
查找峰值元素的时间复杂度是多少？
二分查找的时间复杂度为 O(log n)，空间复杂度为 O(1)，对于 5000 个值，最多需要 13 步。从左侧开始遍历的时间复杂度为 O(n)，因为找到下降点之前，它可能会读取每一对值。
有多个峰值时，二分查找仍然有效吗？
是的，只要相邻值不同，并且两端之外的位置都视为低于所有值即可。它会返回一个峰值，但不一定是最高值。向上走一步后，最迟到范围末尾时，数值必须转为向下，而第一次转向的位置就是峰值，因此搜索保留的一侧始终至少有一个峰值。
峰值总是最大值吗？
在这道题中，是的：数组先升到一个峰值，然后下降，所以没有其他值会更大。在有多个峰值的版本中则不是这样，因为任何比左右两边的值都大的值都算作峰值。这就是为什么搜索时要比较相邻的值，而不是寻找最大值。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def findPeakElement(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [2, 5, 9, 4, 1]
预期输出
2