162. 寻找峰值

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）暴力求解
  
  （2）二分法