寻找peak元素

面试问到的算法题。

Problem

给定一个数组（元素为数字），数组内的值相邻的两个元素值不同，如果一个元素的左右两边的元素值都小于该元素，则该元素为peak元素（对于两个端点元素一边符合即可）。

要求返回一个peak元素即可。

算法的时间复杂度越小越好。

Solution

采用暴力解法的时间复杂度为O(n)。

如果采用二分查找可以将时间复杂度降到O(logn)。

可以用二分查找，寻找中间点，如果中间点大于右边的点，那么左半边（包含中间点在内）一定有一个点符合peak，反之一样。这样不断地每次缩小1/2的范围最终就可以使用O(logn)的时间复杂度找到peak点。

Code

ts

const findPeak = (mountains: number[]): number => {
    let left: number = 0
    let right: number = mountains.length - 1
    
    while (left < right) {
        // 找到中间点
        let mid: number = Math.floor((left + right) / 2)
        
        if (mountains[mid] > mountains[mid + 1]) {
            // 左半边一定有peak
            right = mid
        } else {
            // 右半边一定有peak
            left = mid + 1
        }
    }
    
    return mountains[left]
}

console.log(findPeak([1,2,3,4,8,5]))
console.log(findPeak([3,2,6,4,8,5]))
console.log(findPeak([1,2,3,4,5]))
console.log(findPeak([5,4,3,2,1]))

Review

1. 本题难点在于想不到可以使用二分查找来缩小查询范围，因为本题的要求是只要找到任意一个peak即可。
2. 要想到在使用二分查找时如果中间点大于右边的点，那么左半边（包含中间点）在内的区间一定存在peak，反之亦然，这样就缩小了一半的范围。