每日leetcode

852. 山脉数组的峰顶索引 - 力扣（LeetCode）

题目

给定一个长度为 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 <= 105
• 0 <= arr[i] <= 106
• 题目数据 保证 arr 是一个山脉数组

思路

1. 题目要求在O(log n)的时间复杂度完成，显然就是要使用二分查找法找最大值。
2. 那么先将数组的左右边界作为二分的左右边界。
3. 每次循环取左右边界的中点。如果中点高于其左侧点（说明左边界到中点还在上坡），就将左边界更新到中点；同理，如果中点高于右侧点（说明右边界到中点还在上坡），就将右边界更新到中点。
4. 更新到最后，中点会大于其左侧点和右侧点，那么这两个边界都会更新到中点，这时两边界相等时就达到山峰了。

代码实现

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 0, right = arr.size()-1;while(left < right) {int middle = (left+right) / 2;if(arr[middle] > arr[middle-1]) left = middle;if(arr[middle] > arr[middle+1]) right = middle;}return left;}
};

复杂度分析

• 时间复杂度：O(log n)。
• 空间复杂度：O(1)。

题解