Leetcode面试经典150题-162.寻找峰值

 解法都在代码里，不懂就留言或者私信

想清楚的话会特别简单，你可能想不到这是个二分。。。

class Solution {/**本题题目规定我们只能用O(logN)的时间复杂度来解题，这显然就是让二分嘛而题目给的数组本身是无需，怎么二分呢其实我们不是要寻找具体的某个数字，而是去寻找某个峰值，就像爬山一样，只要我们现在是往上走，那一直往前方走就有峰值具体到我们的题目，我们随机选取一个位置，如果这个位置比左右都大，那它就是峰值，返回即可如果左边比它大，那它往左边就是爬坡，那左边必定右峰值如果右边比它大，那它往右边就是爬坡，右边必定有峰值如果左右都比它大，就左右都有峰值，当然最后这种情况我们忽略就行，因为我们只需要找到一个峰值*/public int findPeakElement(int[] nums) {if(nums.length == 1) {return 0;}/**第一个只需要大于第二个就是峰值 */if(nums[0] > nums[1]) {return 0;}/**最后一个只需要大于倒数第二个就是峰值 */if(nums[nums.length-1] > nums[nums.length - 2]) {return nums.length - 1;}/**如果第一个和最后一个都不是峰值，我们从1~nums.length-2里找*/int left = 1;int right = nums.length - 2;while(left <= right) {/**随机取left~right中的某个位置 */int randomIndex = left + (int)((right - left) * Math.random());/**如果比左右都大，那不就是我们的答案吗，这么写不会越界吗？不会，因为我们是在第二个~倒数第二个之间尝试的*/if(nums[randomIndex] > nums[randomIndex-1] && nums[randomIndex] > nums[randomIndex + 1]) {return randomIndex;/**右边大，右边肯定有峰值 */} else if(nums[randomIndex+1] > nums[randomIndex]) {left = randomIndex + 1;} else {/**左边大，左边肯定有峰值 */right = randomIndex - 1;}}return -1;}
}