符合下列属性的数组 arr 称为 山脉数组 ：
arr.length >= 3- 存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < ... arr[i-1] < arr[i]arr[i] > arr[i+1] > ... > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ，返回满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。
你必须设计并实现时间复杂度为 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 <= 1050 <= arr[i] <= 106- 题目数据保证
arr是一个山脉数组
解题思路
很明显我们是能看出数组的 ”二段性“ 的，可以把数组分为下面两个区间：
此时 mid 有三种情况：
- 如果
mid落在上升区间中，说明[left, mid]区间是可以舍弃的，所以直接left = mid + 1 - 如果
mid落在下降区间中，说明[mid, right]区间是可以舍弃的，所以直接right = mid - 1 - 如果
mid就是山峰，那么直接返回结果即可
重复上述的操作，直到 left ≥ right 为止！
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left = 0, right = arr.size() - 1;
while(left < right)
{
int mid = left + (right - left + 1) / 2; // 这里需要+1，不然左边界会越界访问
if(arr[mid - 1] < arr[mid] && arr[mid] < arr[mid + 1])
left = mid + 1;
else if(arr[mid - 1] > arr[mid] && arr[mid] > arr[mid + 1])
right = mid - 1;
else
return mid;
}
return left;
}
};套用求右边界模板
其实这道题还是可以用我们的模板来解决的，如下图所示：
此时 mid 有两种情况：
- 如果
mid落在红色区间，即arr[mid] > arr[mid - 1]，此时[left, mid - 1]是可以舍去的，但是不能舍去mid，因为mid可能就是山峰，所以让left = mid即可！ - 如果
mid落在绿色区间，即arr[mid] < arr[mid - 1]，此时[mid, right]都是可以舍去的，因为山峰规定不包括在该区间内，所以让right = mid - 1即可！
从上面的情况来看，套用的就是求右边界的模板，如下所示：
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left = 0, right = arr.size() - 1;
while(left < right)
{
int mid = left + (right - left + 1) / 2;
if(arr[mid] > arr[mid - 1])
left = mid;
else
right = mid - 1;
}
return left;
}
}; 当然，这道题套用求左边界的模板也是一样的，这里只举求右边界的模板为例！