21. 山峰数组的峰顶索引

算法思路
解决这类问题的关键在于理解山脉数组的特性。峰顶元素同时大于其左右相邻值,左侧呈上升趋势,右侧呈下降趋势。这种单调性天然适合二分查找。
我们关注中间位置 mid 与其相邻元素的关系:
- 若
arr[mid] < arr[mid + 1],说明处于上升阶段,峰值在右侧; - 若
arr[mid] > arr[mid + 1],说明处于下降阶段,峰值在左侧或即为当前点。
通过不断缩小搜索范围,最终收敛到峰顶索引。
C++ 算法代码
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left = 0;
int right = arr.size();
while(left < right) {
int mid = left + (right - left) / 2;
// 对于偶数而言 mid 始终是在左边,所以判断条件是 arr[mid] < arr[mid + 1]
if(arr[mid] < arr[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
};





