红豆稀饭
0%

162-寻找峰值

发表于 阅读次数： Valine：

题目地址：https://leetcode.cn/problems/find-peak-element

题目

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

思路

直接循环遍历，找到第一个大于左右相邻值的元素即可。关键在于如果数组是有序递增或者递减的数组，就得用一个值来存储最大值。

代码

方法一 直接遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function(nums) {
    if(nums.length === 1) return 0
    let ans = -Infinity
    for(let i = 0; i < nums.length; i ++) {
        if(nums[i] > nums[i+1] && nums[i] > nums[i-1]) {
            return i
        }
        ans = Math.max(ans, nums[i])
    }
    return nums.indexOf(ans)
};

方法二 双端遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function(nums) {
    if(nums.length === 1) return 0
    let ans = -Infinity
    let left=0, right=nums.length-1
    while(left <= right) {
        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
        }
        ans = Math.max(ans, nums[left], nums[right])
        left++
        right--
    }
    return nums.indexOf(ans)
};