162. Find Peak Element

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @return {number}
 */

题目给我们一个未排序的数字数组 nums

要求我们求出数组中任一的 peak 下标是多少

peak 的定义就是左右两边的元素都小于它，我们把 nums[-1] 与 nums[nums.length] 都认为是负无穷

最后返回符合条件的任一下标

解题思路

由于这题要求我们用 O(logn) 的复杂度来求解

所以会需要用到二分搜索的思路来做

套路还是一样的，我们先规定左边界 left 为 0、右边界 right 为 nums.length

接着我们进入遍历，计算 mid = Math.floor((left + right) / 2)

接下来我们需要比较 nums[mid] 与 nums[mid+1] 的值，有两种可能：

1. nums[mid] > nums[mid+1] ：此时 mid 可能为 peak，所以我们需要更新 right = mid
2. nums[mid] <= nums[mid+1] ：此时 mid 不可能为 peak，所以需要更新 left = mid+1

由于题目只需要我们找到任一 peak 即可，所以我们重复上述遍历过程最后返回 left 即可

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function(nums) {
    let left = 0
    let right = nums.length

    while(left < right) {
        let mid = Math.floor((left + right) / 2)

        if(nums[mid + 1] > nums[mid]) {
            // current mid isn't the peak
            left = mid + 1
        } else {
            // current mid might be a peak
            right = mid
        }
    }
    return left
};

复杂度分析

时间

O(logn)

空间

O(1)