题解 | #寻找峰值#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int findPeakElement (int[] nums) {
        // write code here
        // 左程云老师讲过局部极值问题，采用二分思想解决

        // 算法的时间复杂度O(logN)，额外空间复杂度O(1)

        // 1.先判断n=1和2的情况
        int n = nums.length;
        if (n == 1) {
            return 0;
        }
        if (n == 2) {
            return nums[0] > nums[1] ? 0 : 1;
        }

        // 2.采用二分思想，确定左右边界，分别考察边界的递增情况
        int l = 0;
        int r = n - 1;
        int mid = 0;
        while (l <= r) {
            mid = (l + r) / 2;
            // 2.1 若两边中有一边出现了极值，直接返回
            if (nums[l] > nums[l + 1]) {
                return l;
            }
            if (nums[r] > nums[r - 1]) {
                return r;
            }
            // 2.2 若两边均未出现极值，说明是[↗……↘] 的情况，则考察中间的mid
            if (nums[mid] > Math.max(nums[mid - 1], nums[mid + 1])) {
                // 若mid处的两边能确定极值，即[↗……↗↘……↘]，则返回mid
                return mid;
            } else if (nums[mid - 1] > Math.max(nums[mid], nums[mid + 1])) {
                // 若mid-1处元素更大，即[↗……↖……↘]，说明极值出现在左半区，修改右边界r
                r = mid - 1;
            } else {
                // 若mid+1处元素更大，即[↗……↗……↘]，说明极值出现在右半区，修改左边界l
                l = mid + 1;
            }
        }
        
        // 3.直到退出了循环，还找不到峰值，则返回-1
        return -1;
    }
}