【优选算法】（第十一篇）

⼭峰数组的峰顶（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;}
}