山脉数组的峰顶索引

难度: Easy

符合下列属性的数组 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 ，即山峰顶部。

示例 1：

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

示例 2：

输入：arr = [1,3,5,4,2]
输出：2

示例 3：

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

示例 4：

输入：arr = [3,4,5,1]
输出：2

示例 5：

输入：arr = [24,69,100,99,79,78,67,36,26,19]
输出：2

提示：

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

进阶：很容易想到时间复杂度 O(n) 的解决方案，你可以设计一个 O(log(n)) 的解决方案吗？

注意：本题与主站 852 题相同：https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/

Submission

运行时间: 16 ms

内存: 16.9 MB

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

Explain

该题解采用二分查找方法寻找山脉数组的峰顶索引。在山脉数组中，由于数组的元素先递增后递减，因此可以通过比较中间元素与其右侧元素的关系来确定峰顶的位置。如果中间元素大于其右侧元素，则峰顶在左侧，包括当前中间位置；如果中间元素小于其右侧元素，则峰顶在右侧。通过不断调整左右边界，缩小查找范围，最终找到峰顶。

时间复杂度: O(log n)

空间复杂度: O(1)

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        left = 0  # 初始化左边界
        right = len(arr) - 1  # 初始化右边界
        while left < right:  # 当左边界小于右边界时继续查找
            mid = (left + right) // 2  # 计算中点位置
            if arr[mid] > arr[mid + 1]:
                right = mid  # 如果中点元素大于其右侧元素，则峰顶在左侧或中点
            else:
                left = mid + 1  # 如果中点元素小于其右侧元素，则峰顶在右侧
        return left  # 最终左边界即为峰顶位置

Explore

在山脉数组中，元素先递增后递减。如果中点元素大于其右侧元素，说明从中点向右的方向不再是递增的，因此中点自身可能是峰顶，或者峰顶在中点的左侧。因此，更新右边界为中点，继续在左半部分寻找可能的峰顶。

如果中点元素小于其右侧元素，表明中点到中点右侧元素之间是递增的，因此峰顶必定在中点的右侧。更新`left`为`mid + 1`是为了排除中点元素，因为已知它不是峰顶。这种更新方式不会跳过峰顶，因为按照山脉数组的特性，峰顶一定在递增序列的右侧。

如果数组全部递增或递减，则不符合山脉数组的定义。山脉数组要求数组中存在一个峰顶，即元素先递增后递减。在完全递增或递减的数组中应用本算法可能导致不正确的结果或无法找到峰顶。在实际应用中，应首先验证数组是否符合山脉数组的定义。如果确认是山脉数组，二分查找方法才是有效的。