题解 | #寻找峰值#

import java.util.*;
//方法一：暴力解法，一次遍历。时间复杂度：O(N)
//方法二：二分法,或者是分治法，时间复杂度为：O(lonN)
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int findPeakElement (int[] nums) {
        // write code here
//         //方法一：暴力解法，一次遍历。时间复杂度：O(N)
//         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;
//         }
//         //第二个元素到倒数第二个元素
//         for(int i=1;i<length-1;i++){
//             if(nums[i]>nums[i-1] && nums[i]>nums[i+1]){
//                 return i;
//             }
//         }
        
//         return 0;
        
        //方法二：二分法,或者是分治法，时间复杂度为：O(lonN)
        
        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 min = 1;//最小值索引
        int max = length-2;//最大值索引
        int mid = (min+max)/2;//中值索引
        int res = peek(min,max,mid,nums);
        
        return res;
    }
    
    public int peek(int min,int max,int mid,int[] nums){
        if(min>max){//递归出口
            return -1;
        }
        if(nums[mid]>nums[mid-1] && nums[mid]>nums[mid+1]){//符合题目条件，返回结果
            return mid;
        }else{
            int max1 = mid-1;//更新最大值
            int temp = peek(min,max1,(min+max1)/2,nums);//左递归
            if(temp != -1){
                return temp;
            }
            int min1 = mid+1;//更新最小值
            temp = peek(min1,max,(mid+1+max)/2,nums);//右递归
            if(temp !=-1 ){
                return temp;
            }
        }
        return -1;
    }
}