0852. 山脉数组的峰顶索引 #

标签：数组、二分查找
难度：简单

题目大意 #

给定由整数组成的山脉数组 arr。

要求：返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[len(arr) - 1] 的下标 i。

山脉数组：满足以下属性的数组。

len(arr) >= 3；
存在 i（0 < i < len(arr) - 1），使得：
- arr[0] < arr[1] < ... arr[i-1] < arr[i];
- arr[i] > arr[i+1] > ... > arr[len(arr) - 1]。

解题思路 #

可以使用二分查找来查找峰值。

使用两个指针 left、right 。left 指向数组第一个元素，right 指向数组最后一个元素。
取区间中间节点 mid，并比较 nums[mid] 和 nums[mid + 1] 的值大小。
- 如果 nums[mid] 小于 nums[mid + 1]，则右侧存在峰值，令 left = mid + 1。
- 如果 nums[mid] 大于等于 nums[mid + 1]，则左侧存在峰值，令 right = mid。
最后，当 left == right 时，跳出循环，返回 left。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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