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;
    }
}