一.题目描述

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

二.题目解析

题目给了我们一个山脉数组，山脉数组的值分布就如下面的样子：

然后我们只需要返回数组的峰值元素的下标即可。 

三.算法原理

1.暴力解法

因为题目明确说明，arr一定是一个山脉数组。所以它一定满足先递增后递减。所以暴力的解法就是遍历数组，找到一个数它既大于前面的数又大于后面的数即可。

时间复杂度：最坏情况下，峰值位于倒数第二个位置，所以时间复杂度为O(N)

空间复杂度：在遍历过程中，只涉及到了几个变量，所以空间复杂度为O(1)

2.二分查找算法

因为题目明确告诉我们这是一个山脉数组，所以它的二段性还是非常明显的。

如图所示，该数组有这样一种二段性。在上升阶段包含峰值，都满足当前位置大于前一个位置，在下降阶段，都满足当前位置小于前一个。

当mid落到左区间，该位置的值有可能就是峰值，所以我们不能让left跳过mid，所以left  = mid；

当mid落到有区间，该位置的值不可能是结果，所以我们直接让right跳过mid，所以right = mid-1. 

因为我们这里并没有单独处理等于的情况，所以这里不能用简单二分，而得用查找区间右端点的写法。

四.代码实现

//C++
//写法1：class Solution 
{
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 1;int right = arr.size()-2;while(left<right){int mid = left+(right-left+1)/2;if(arr[mid]>arr[mid-1]){left = mid;}else{right = mid-1;}}return left;}
};//写法二：
class Solution 
{
public:int peakIndexInMountainArray(vector<int>& arr) {int ret = 0;int left = 0;int right = arr.size()-1;while(left<=right){int mid = left+(right-left)/2;if(arr[mid] > arr[mid-1] && arr[mid] < arr[mid+1]){left = mid;}else if(arr[mid] < arr[mid-1] && arr[mid] > arr[mid+1]){right = mid;}else{ret = mid;break;}}return ret;}
};

# pythonclass Solution:def peakIndexInMountainArray(self, arr: List[int]) -> int:left,right = 1,len(arr)-2while left<right:mid = left+(right-left+1)//2if arr[mid]>arr[mid-1]:left = midelse:right = mid - 1return left