目录
⼭峰数组的峰顶（easy）
题目解析
讲解算法原理
编写代码
寻找峰值（medium）
题目解析
讲解算法原理
编写代码
⼭峰数组的峰顶（easy）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
符合下列属性的数组 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 。
⽰例1：
输⼊： arr = [0,1,0]
输出： 1
⽰例2：
输⼊： arr = [0,2,1,0]
输出： 1
⽰例3：
输⼊： arr = [24,69,100,99,79,78,67,36,26,19]
输出： 2
讲解算法原理
解法⼀（暴⼒查找）：
算法思路：
峰顶的特点：⽐两侧的元素都要⼤。
因此，我们可以遍历数组内的每⼀个元素，找到某⼀个元素⽐两边的元素⼤即可。
算法代码：
class Solution {
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;
}
};解法⼆（⼆分查找）：
算法思路：
1. 分析峰顶位置的数据特点，以及⼭峰两旁的数据的特点：
◦ 峰顶数据特点： arr[i] > arr[i - 1] && arr[i] > arr[i + 1] ；◦ 峰顶左边的数据特点： arr[i] > arr[i - 1] && arr[i] < arr[i + 1] ，也就是
呈现上升趋势；
◦ 峰顶右边数据的特点： arr[i] < arr[i - 1] && arr[i] > arr[i + 1] ，也就是
呈现下降趋势。
2. 因此，根据 mid 位置的信息，我们可以分为下⾯三种情况：
◦ 如果 mid 位置呈现上升趋势，说明我们接下来要在 [mid + 1, right] 区间继续搜索；◦ 如果 mid 位置呈现下降趋势，说明我们接下来要在 [left, mid - 1] 区间搜索；
◦ 如果 mid 位置就是⼭峰，直接返回结果。
编写代码
c++算法代码：
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;
}
};java算法代码：
class Solution
{
public int peakIndexInMountainArray(int[] arr)
{
int left = 1, right = arr.length - 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;
}
}寻找峰值（medium）
题目解析
1.题目解析：. - 力扣（LeetCode）
2.题目描述：
峰值元素是指其值严格⼤于左右相邻值的元素。
给你⼀个整数数组nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何⼀个峰值所在位置即可。
你可以假设nums[-1]=nums[n]=-∞。
你必须实现时间复杂度为O(logn)的算法来解决此问题。
⽰例1：
输⼊：nums=[1,2,3,1]
输出：2
解释：3是峰值元素，你的函数应该返回其索引2。
⽰例2：
输⼊：nums=[1,2,1,3,5,6,4]
输出：1或5
解释：你的函数可以返回索引1，其峰值元素为2；
或者返回索引5，其峰值元素为6。
提⽰：
1<=nums.length<=1000
-231<=nums[i]<=231-1
对于所有有效的i都有nums[i]!=nums[i+1]
讲解算法原理
解法⼆（⼆分查找算法）：
算法思路：
寻找⼆段性：
任取⼀个点 i ，与下⼀个点 i + 1 ，会有如下两种情况：
• arr[i] > arr[i + 1] ：此时「左侧区域」⼀定会存在⼭峰（因为最左侧是负⽆
穷），那么我们可以去左侧去寻找结果；
• arr[i] < arr[i + 1] ：此时「右侧区域」⼀定会存在⼭峰（因为最右侧是负⽆
穷），那么我们可以去右侧去寻找结果。
当我们找到「⼆段性」的时候，就可以尝试⽤「⼆分查找」算法来解决问题。
编写代码
c++算法代码：
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;
}
};java算法代码：
class Solution
{
public int peakIndexInMountainArray(int[] arr)
{
int left = 1, right = arr.length - 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;
}
}
