题解 | #寻找峰值#
寻找峰值
https://www.nowcoder.com/practice/fcf87540c4f347bcb4cf720b5b350c76
使用二分查找
注意：题目是找峰值元素，不是找最大值
所以找到的波峰不一定是最大值，但它一定是一个峰的峰顶
具体做法：
- step 1：二分查找首先从数组首尾开始，每次取中间值，直到首尾相遇。
- step 2：如果中间值的元素大于它右边的元素，说明往右是向下，我们不一定会遇到波峰，但是那就往左收缩区间。
- step 3：如果中间值小于右边的元素，说明此时往右是向上，向上一定能有波峰，那我们往右收缩区间。
- step 4：最后区间收尾相遇的点一定就是波峰。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int findPeakElement(vector<int>& nums) {
// write code here
int low = 0;
int high = nums.size()-1;
while(low < high)//一般退出条件为low == high，除非数组长度不正常
{
int mid = (low + high)/2;
//右边是往下，不一定能找到波峰,所以往左边找
if(nums[mid] > nums[mid + 1])
high = mid;//要使条件能到达low == high，则high不能为mid-1，必须为mid
else //右边是往上，一定能找到波峰，所以往右边找
low = mid+1;
}
return high;
}
};
投递喜马拉雅等公司6个岗位