文章目录
- 1.题目
- 2.思路
- 3.代码
1.题目
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
2.思路
通过比较中间元素 nums[mid] 和其右侧元素 nums[mid + 1]，如果 nums[mid] < nums[mid + 1]，说明峰值在右侧，因此移动左指针；否则，峰值在左侧或当前中间元素处，因此移动右指针。最终，当左右指针相遇时，左指针的位置即为山脉数组的峰值索引。
3.代码
class Solution {
public:int peakIndexInMountainArray(vector<int>& nums) {// 初始化左右指针，left 指向数组的起始位置，right 指向数组的末尾int left = 0, right = nums.size() - 1;// 使用二分查找法，在左右指针重合之前不断缩小查找范围while (left <= right) {// 计算中间位置，避免直接相加可能导致整数溢出int mid = left + (right - left) / 2;// 如果中间位置的元素小于其右边的元素，说明峰值在右侧if (nums[mid] < nums[mid + 1]) {left = mid + 1; // 将左指针移动到 mid 的右侧} else {// 否则，说明峰值可能在 mid 或其左侧right = mid - 1; // 将右指针移动到 mid 的左侧}}// 当循环结束时，left 指向的就是峰值所在的索引return left;}
};
