Java实现#寻找峰值#

从此题中得到的小感悟 ：充分把握题意方能选用更合适的解题方法（类二分法）

• 此题难度中等，很容易想到思路1，但是仅此的话，不符合“中等”的标签；另外，题中要求时间复杂度为 O(log n)，这让我们很自然地联想到二分法，我们所熟悉的二分法是基于有序表，这道题目数组并不一定有序，那又如何和二分法产生关联呢？读题！读题！读题！分析题目！

思路1：模拟。

• 遍历nums,对于nums[i],检查满足 nums[i] > nums[i-1]并且nums[i] > nums[i+1]的情况，返回下标i即可。
• 需要注意的是，边界情况。题目给定nums[-1] = nums[n] = -∞，所以nums[0] > nums[1] 或 nums[n-1] > nums[n-2]也为峰值

复杂度

• 时间复杂度O(n),空间复杂度O(1)

代码（Java实现）

public class Solution {
	public int findPeakElement (int[] nums) {
        int n=nums.length;
        if(n==1) return 0;
        if(n>=2) { //左边界和右边界单独判断
        	if(nums[0]>nums[1])   return 0;
        	if(nums[n-1]>nums[n-2]) return n-1;
        }
        for(int i=1;i<=n-2;i++) {
        	if(nums[i]>nums[i-1]&&nums[i]>nums[i+1]) return i;
        }
        
        return -1;
    }
}

思路2：类二分法.（比较简洁且符合要求）

借鉴了《画解剑指 Offer》作者大鹏的思路。 链接：https://leetcode-cn.com/problems/find-peak-element/solution/hua-jie-suan-fa-162-xun-zhao-feng-zhi-by-guanpengc/

我把它称之为类二分法，就是类似二分法的意思，而不把它称之为二分法，区别严格意义上的二分法

过程：

• 首先要注意题目条件，在题目描述中出现了 nums[-1] = nums[n] = -∞，这就代表着 只要数组中存在一个元素比相邻元素大，那么沿着它一定可以找到一个峰值
• 根据上述结论，我们就可以使用二分查找找到峰值.
• 查找时，左指针 left，右指针 right，以其保持左右顺序为循环条件.
• 根据左右指针计算中间位置 mid，并比较 mid 与 mid+1 的值，如果 mid 较大，则左侧存在峰值，right = mid，如果 mid + 1 较大，则右侧存在峰值，left = mid + 1 .
• 一定要好好理解和体会上面第一句话的表达，

复杂度

• 时间复杂度O(log n),空间复杂度O(1)

代码（Java实现）

public class Solution {
	public int findPeakElement (int[] nums) {
       int left=0,right=nums.length-1;
		int mid=0;
		while(left<right) {
		    mid=left+(right-left)/2;//增量式取区间中点
			if(nums[mid]<nums[mid+1]) left=mid+1;//右侧存在峰值
			else right=mid;//左侧存在峰值
		}
		return left;
    }
}

Q：

• 对于思路2中的代码，有小伙伴可能有 疑惑：if 判断中 mid+1 不加限制难道不会越界吗？

A:

• 答案是不会越界。首先你能提出这样的问题，祝贺你很爱思考问题，下面我会用数学知识证明 mid+1不会发生数组下标越界，不需要加以限制。

数学证明：

这下明白了吧