网站建立教学_长沙百家号seo_怎样建网站卖东西_企业网络营销推广平台

---

题目链接：

852. 山脉数组的峰顶索引

---

题目描述：

---

解法

暴力解法：

若：arr=[0,1,2,3,2,1,0]

可以定义一个指针指向第一个元素，如果它后面的元素比它大，那么他就不是峰值。

当第一次遇到一个数是大于后面那个数的时候，那个数就是峰值。

二分算法：

这边天然的出现了二段性。

这边有一个细节，就是题目给的都是山峰数组，也就意味着数组的开头和结尾两个元素不会是山峰，所以left下标从1开始，right下标从size-2开始。

---

C++ 算法代码：

暴力解法：

public:
int peakIndexInMountainArray(vector<int>& arr) {int n = arr.size();// 遍历数组内每一个元素，直到找到峰顶for (int i = 1; i < n - 1; i++) // 峰顶满足的条件if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1])return i; // 为了处理 oj 需要控制所有路径都有返回值return -1;
}
};

二分查找：

class Solution 
{public:int peakIndexInMountainArray(vector<int>& arr) {int left = 1, 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;}
};

---

图解

例如：arr=[0,1,2,3,2,1,0]

1. left = 1, right=5

   进入循环，mid=3

   满足arr[mid] > arr[mid - 1]，left = mid=3

2. left = 3, right=5

   进入循环，mid=4

   right = mid - 1=3

3. left = 3, right=3

   结束循环，返回3