LeetCode 852：山脉数组的峰顶索引解析与实现
LeetCode 852：山脉数组的峰顶索引解析与实现
题目描述
给定一个长度为 n 的整数山脉数组 arr，其中的值先递增到一个峰值元素，然后递减。
要求返回峰值元素的下标。
题目要求必须设计并实现时间复杂度为 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^5
- 0 <= arr[i] <= 10^6
- 题目数据保证 arr 是一个山脉数组
问题分析
这道题目是经典的二分查找应用场景。所谓山脉数组，就是先递增后递减的数组，类似于一座山的形状。我们需要找到山顶的位置，也就是数组中的最大值的索引。
根据题目要求，时间复杂度必须是 O(log(n))，这明确提示我们应该使用二分查找算法。
解题思路
- 在山脉数组中，对于峰值左侧的元素，有
arr[i] < arr[i+1] - 对于峰值右侧的元素，有
arr[i] > arr[i+1] - 峰值元素同时满足
arr[i-1] < arr[i]和arr[i] > arr[i+1]（如果索引有效）
利用这些性质，我们可以通过二分查找快速定位峰值的位置：
- 如果
arr[mid] < arr[mid+1]，说明 mid 在峰值左侧，峰值在右半部分 - 如果
arr[mid] > arr[mid+1]，说明 mid 可能是峰值或者在峰值右侧，峰值在左半部分（包括 mid）
代码实现
class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {// 初始化左右边界int left = 0;int right = arr.size() - 1;// 二分查找过程while (left < right) {// 计算中间位置int mid = left + (right - left) / 2;// 如果中间元素小于其右侧元素，说明峰值在右侧if (arr[mid] < arr[mid + 1]) {