Leetcode162:寻找峰值

一、题目

峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 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。

二、题解

局部最大定义：在一个无序数组中，相邻的数肯定不相等。找到任意一个局部最大数；
边界处理：

• 如果数组第一个比第二个大，那么第一个肯定是局部最大。
• 如果数组最后一个数比倒数第二个数大，那么最后一个数肯定是局部最大。

如果不满足以上边界，说明左侧呈上升趋势，右侧呈下降趋势，又因为相邻的数不相等，那么中间一定会存在一个局部最大的数。

使用二分法，取出中间的数：

• 如果中间的数mid比mid-1大，也比mid+1大，那么中间的数一定是局部最大。
• 如果中间的数mid比mid-1小，那么从0到mid-1中一定存在一个局部最大，直接从左侧中找局部最大。
• 如果中间的数mid比mid+1小，那么从mid到数组结尾一定存在一个局部最大，直接从右侧中找局部最大。

class Solution {
    public int findPeakElement(int[] nums) {
        int length = nums.length;
        if(length==1){
            return 0;
        }
        if(nums[0]>nums[1]){
            return 0;
        }
        if(nums[length-1]>nums[length-2]){
            return length-1;
        }
        int left = 0;
        int right = length-1;
        while(left<=right){
            int midIndex = (left+right)/2;
            if(midIndex==0){
                return 1;
            }
            if(midIndex==length-1){
                return length-2;
            }
            if((midIndex-1)==0 && nums[midIndex] > nums[midIndex+1]){
                return midIndex;
            }
            if((midIndex+1)==length && nums[midIndex]>nums[midIndex -1]){
                return midIndex-1;
            }
            if(nums[midIndex]>nums[midIndex-1] && nums[midIndex]>nums[midIndex+1]){
                return midIndex;
            }
            if(nums[midIndex] < nums[midIndex -1]){
                right = midIndex -1 ;
            }else{
                left = midIndex +1;
            }
        }
        return -1;
    }
}