山脉数组的峰顶索引

难度: Medium

符合下列属性的数组 arr 称为 山脉数组 ：

arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
- arr[0] < arr[1] < ... arr[i-1] < arr[i]
- arr[i] > arr[i+1] > ... > arr[arr.length - 1]

给你由整数组成的山脉数组 arr ，返回满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。

你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

示例 1：

输入：arr = [0,1,0]
输出：1

示例 2：

输入：arr = [0,2,1,0]
输出：1

示例 3：

输入：arr = [0,10,5,2]
输出：1

提示：

3 <= arr.length <= 10⁵
0 <= arr[i] <= 10⁶
题目数据保证 arr 是一个山脉数组

Submission

运行时间: 24 ms

内存: 27.8 MB

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        l = 0
        r = len(arr) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if arr[mid] < arr[mid + 1]:
                l = mid + 1
            else:
                r = mid - 1
        
        return l

Explain

这个题解使用了二分查找的思路。因为题目保证输入数组 arr 是一个山脉数组，满足先升序再降序的特点，而我们要找的就是数组的最高点。二分查找可以用来在有序数组中高效地查找目标元素，而这里的 arr 虽然整体不是有序的，但在最高点左侧是升序、右侧是降序，所以可以通过比较 arr[mid] 与 arr[mid+1] 的大小关系来缩小查找范围，最终找到最高点。

时间复杂度: O(log n)

空间复杂度: O(1)

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        l = 0
        r = len(arr) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if arr[mid] < arr[mid + 1]:  # 如果 mid 处的元素小于右邻居，说明最高点在右侧
                l = mid + 1
            else:  # 如果 mid 处的元素大于等于右邻居，说明最高点在左侧（包括 mid）
                r = mid - 1
        
        return l  # 循环结束时，l 指向的就是最高点的索引

Explore

在山脉数组中，数组先增后减。当 arr[mid] < arr[mid + 1] 时，说明从 mid 到 mid+1 处于上升阶段，因此最高点（即峰顶）必然在 mid 右侧的某处。因为如果最高点在 mid 左侧或者是 mid，那么 arr[mid] 应该大于或等于 arr[mid + 1]。

在真正的山脉数组中，arr[mid] 等于 arr[mid + 1] 的情况不会出现。山脉数组的定义是严格升序后严格降序，不存在连续相等的元素。如果在异常情况下出现这种情况，可能意味着输入的数组不符合山脉数组的定义。

二分查找过程中，l 和 r 不断调整以缩小查找范围。当 arr[mid] >= arr[mid + 1]，即可能在峰顶或其左侧时，r 被设置为 mid-1；当 arr[mid] < arr[mid+1] 时，l 被设置为 mid+1。最终，当 l > r 时循环结束，此时 l 恰好指向峰顶的位置，因为在最后一次条件判断中，l 移动到了峰顶的位置。

虽然山脉数组整体不是完全有序的，但其特性是分为严格升序和严格降序两部分。这允许我们使用二分查找的逻辑：通过比较中点与相邻点的关系，我们可以确定峰顶在左侧还是右侧，从而有效地缩小查找范围。这种方法利用了山脉数组的局部有序性（即升序或降序部分），使得二分查找成为可能。