LeetCode——寻找峰值

NO.162 寻找峰值 中等

思路一：二分法 数组搜索时间复杂度要求 O(logN)，第一个就应该想到二分查找，但是本题的数组是个无序数组，但是我们并不需要其有序，因为知道”山峰”的特点：相较于左边部分是递增的，相较于右边部分是递减的。

当 nums[mid] > nums[mid+1] 时，根据特点知道山峰一定在[left,mid]区间内；否则山峰在[mid+1,right]区间内。根据这个特点就可以对搜索区间折半收缩。

搜索结束条件是搜索区间内只剩下一个元素，即为山峰；选择搜索区间是左闭右闭的[left,right]，所以结束条件是 left == right。

public int findPeakElement(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + ((right - left) >>> 1);
        if (nums[mid] > nums[mid + 1]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

时间复杂度：O(logn)

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github