🌕 162. 寻找峰值

难度: 🌕

问题描述

---

解法

class Solution {
    public int findPeakElement(int[] nums) {
        // 思路：
        // 二分
        int len = nums.length;
        if(len == 1) {
            return 0;
        }
        if(nums[0] > nums[1]) {
            return 0;
        } 
        if(nums[len - 1] > nums[len - 2]) {
            return len - 1;
        }
        // 排除 左右边界的干扰
        return mySol(nums, 1, len - 2);
    }

    private int mySol(int[] nums, int left, int right) {
        // 递归终止条件
        if(left >= right) {
            if(nums[left] > nums[left - 1] && nums[left] > nums[left + 1]) {
                return left;
            } else {
                return -1; // 这个区间不存在合适的索引
            }
        }
        if(nums[left] > nums[left - 1] && nums[left] > nums[left + 1]) {
            return left;
        }
        if(nums[right] > nums[right - 1] && nums[right] > nums[right + 1]) {
            return right;
        }
        // 排除左右边界的干扰
        if(left == right - 1) {
            return -1; // 只有 2 个节点，左右边界又不存在峰值，那么此时整个数组均没有合适的索引
        }
        // 至少 3 个节点 - mid 必 != left
        int mid = left + ((right - left) >> 1);
        if(nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
            return mid;
        } else {
            // 中点不满足条件，无法判断接下来到底是哪个区间，左右区间均查询，遇到 -1 直接转另一区间
            int tmp = mySol(nums, left, mid - 1);
            if(tmp > 0) {
                return tmp;
            } else {
                return mySol(nums, mid + 1, right);
            }
        }
    }
}

---

输出