LeetCode刷题【162】寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 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]

乍得一眼看起来很简单，今天的每日一题，直接上来一个遍历啊，比较前后的大小关系，且题面中也说明了数组边界前一位和后一位都为负无穷，且相邻两位的数值保证不相等

class Solution {
    public int findPeakElement(int[] nums) {
        if (nums.length == 1){
            return 0;
        }
        int i = 0;
        while (i< nums.length){
            if (getArrIndex(nums,i-1)< getArrIndex(nums,i) && getArrIndex(nums,i) > getArrIndex(nums,i+1)){
                return i;
            }
            i++;
        }
        return i;
    }

    public int getArrIndex(int[] nums,int index){
        if ( index<0 || index >= nums.length ){
            return Integer.MIN_VALUE;
        }
        return nums[index];
    }
}

提交，也过了，不过这边其实是有问题的，主要是以下两点

1.复杂度要求的O（Log N），单次全数组遍历的话，时间复杂度在O（N），并不符合题面中要求的O（Log N）。而因为题面的说的

导致遍历的时间消耗其实并不是很大。

2.Integer.MIN_VALUE的问题，因为入参给的就是int[]，导致最小值就是Integer.MIN_VALUE，实际并不是负无穷，而测试用例里就有一个这个用例，但是因为要求的数组中相邻的两个值不相等，且在代码里判断了数组长度为1导致规避掉了这个问题，实际在逻辑上来说，这个作法是错误的

那么接下来，因为要求的O（Log N）时间复杂度，就自然会想到往二分查找的方向上去靠拢。

如果有曲线的话，可以对比下看下，如果当前值比后面的值小，则说明需要往后挪，则left指针往后挪动，否则把right指针往前挪动。在新的方法中我也把比较边界外的值单独写了方法比较，而不是假设定为Integer.MIN_VALUE

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0,r = nums.length-1;
        while (l < r){
            int mid = l + (( r - l )>>1);
            if (isTop(nums,mid)){
                return mid;
            }
            if (compareToNext(nums, mid)){
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        return l;


    }

    boolean compareToNext(int[] nums, int index){
        if (index == nums.length-1){
            return true;
        }
        return nums[index] > nums[index+1];
    }

    boolean isTop(int[] nums, int index){
        boolean leftSmaller,rightSmaller;
        if (index == 0){
            leftSmaller = true;
        }else{
            leftSmaller = nums[index] > nums[index-1];
        }
        if (index == nums.length-1){
            rightSmaller = true;
        }else{
            rightSmaller = nums[index] > nums[index+1];
        }
        return leftSmaller && rightSmaller;
    }
}