2021-02-07 | 162. 寻找峰值

古城微笑少年丶 2022-11-03 11:06 118阅读 0赞

### 1. 题目描述 ###

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

给你一个输入数组 `nums`，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 **任何一个峰值** 所在位置即可。  
你可以假设 `nums[-1] = nums[n] = -∞` 。

**示例 1：**

输入：nums = [1,2,3,1]
    输出：2
    解释：3 是峰值元素，你的函数应该返回其索引 2。

**示例 2：**

输入：nums = [1,2,1,3,5,6,4]
    输出：1 或 5 
    解释：你的函数可以返回索引 1，其峰值元素为 2；
         或者返回索引 5， 其峰值元素为 6。

**提示：**

*  `1 <= nums.length <= 1000`
 *  `-2 <= nums[i] <= 2 - 1`
 *  对于所有有效的 `i` 都有 `nums[i] != nums[i + 1]`

### 2. 解题思路 ###

对于这道题目，最直接的方法就是暴力求解，直接遍历数值，如果数组的元素比两边的元素都大，直接返回它的索引值即可。

对于数组的第一个值和最后一个值，我们需要单独进行判断，因为题目中说了`nums[-1] = nums[n] = -∞`，所以第一个值只要比第二个值大，最后一个值只要比倒数第二个值大，就满足条件，直接返回索引值即可。

**复杂度分析：**

*  时间复杂度：O(n)，其中n是数组的长度，最差的情况下，我们需要遍历完整个数组，所以时间复杂度为O(n)；
 *  空间复杂度：O(1)，这里不需要额外的空间，所以空间复杂度为O(1)。

这样做时间复杂度比较高，我们可以使用**二分法**来解决这个问题，以降低时间复杂度。定义两个指针left和right，根据左右指针来计算他们中间位置mid，并比较mid和mid+1的值，如果mid大，则mid左侧存在峰值，如果mid+1大，那么m右侧存在峰值，这样不断减小两个指针之间的范围，就可以找到目标值。

**复杂度分析：**

*  时间复杂度：O(logn)，其中n是数组的长度，二分查找的时间复杂度为O(logn)；
 *  空间复杂度：O(1)，这里需要的空间为常量，所以空间复杂度为O(1)。

### 3. 代码实现 ###

**（1）暴力求解**

/** * @param {number[]} nums * @return {number} */
    var findPeakElement = function(nums) { 
        const len = nums.length
        if(!len){ 
            return 0
        }
        if(nums[0] > nums[1]){ 
            return 0
        }
        if(nums[len - 1] > nums[ len - 2]){ 
            return len - 1
        }
        for(let i = 1; i < len; i++){ 
            if(nums[i] > nums[i - 1] && nums[i] > nums[i + 1]){ 
                return i
            }
        }
        return 0
    };

**（2）二分法**

/** * @param {number[]} nums * @return {number} */
    var findPeakElement = function(nums) { 
        let left = 0, right = nums.length - 1
        while(left < right){ 
            const mid = Math.floor(left + (right - left) / 2)
            if(nums[mid] > nums[mid + 1]){ 
                right = mid
            }else{ 
                left = mid + 1
            }
        }
        return left
    };

### 4. 提交结果 ###

**（1）暴力求解**  
![在这里插入图片描述][20210227192454721.png]

**（2）二分法**  
![在这里插入图片描述][20210227192519385.png]

[20210227192454721.png]: /images/20221024/e4d92da6f0bf457c83ebdfcbf83bf2fa.png?
[20210227192519385.png]: /images/20221024/b3a6774a100f41b9b35ee403ba9e3d3d.png?