852. 山脉数组的峰顶索引

Problem#

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

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

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

https://leetcode.cn/problems/peak-index-in-a-mountain-array/description/

示例 1：

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

示例 2：

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

示例 3：

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

约束：

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

思路#

解法 1：线性扫描#

遍历直到找到 arr[i] > arr[i + 1] 的位置。

解法 2：二分查找#

山脉数组的峰顶就是「第一个下降点」，可以用二分查找在 O(log n) 时间内找到。

1
class Solution:
2
    def peakIndexInMountainArray(self, arr: list[int]) -> int:
3
        left, right = 0, len(arr) - 1
4
        while left < right:
5
            mid = (left + right) // 2
6
            if arr[mid] < arr[mid + 1]:
7
                left = mid + 1
8
            else:
9
                right = mid
10
        return left

1
import unittest
2

3

4
class TestPeakIndexInMountainArray(unittest.TestCase):
5
    def setUp(self):
6
        self.solution = Solution()
7

8
    def test_example1(self):
9
        self.assertEqual(self.solution.peakIndexInMountainArray([0, 1, 0]), 1)
10

11
    def test_example2(self):
12
        self.assertEqual(self.solution.peakIndexInMountainArray([0, 2, 1, 0]), 1)
13

14
    def test_example3(self):
15
        self.assertEqual(self.solution.peakIndexInMountainArray([24, 69, 100, 99, 79, 78, 67, 36, 26, 19]), 2)
16

17
    def test_large(self):
18
        self.assertEqual(self.solution.peakIndexInMountainArray([1, 2, 3, 4, 5, 3, 1]), 4)
19

20

21
if __name__ == '__main__':
22
    unittest.main()