元素峰值

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

题一、寻找峰值

---

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

示例1:

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

示例2:

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

方案A、迭代爬坡+二分查找

思路:如果 nums[i]<nums[i+1]，并且我们从位置 i 向右走到了位置 i+1，那么位置 i 左侧的所有位置是不可能在后续的迭代中走到的。我们知道位置 i+1 以及其右侧的位置中一定有一个峰值，因此我们可以设计出如下的一个算法:

• 对于当前可行的下标范围 [l,r]，我们随机一个下标 i
• 如果下标 i 是峰值，我们返回 i 作为答案
• 如果 nums[i]<nums[i+1]，那么我们抛弃 [l,i] 的范围，在剩余 [i+1,r] 的范围内继续随机选取下标
• 如果 [i+1]nums[i]>nums[i+1]，那么我们抛弃 [i,r] 的范围，在剩余 [l,i−1] 的范围内继续随机选取下标

在上述算法中，如果我们固定选取 i 为 [l, r] 的中点，那么每次可行的下标范围会减少一半，成为一个类似二分查找的方法，时间复杂度为 O(logn)。

理解:

• get(): 辅助函数,输入下标 i,返回一个二元组 [0/1, nums[i]] , 方便处理 nums[-1] 以及 nums[n] 的边界情况

实现

function get(nums, index) {
  if (index === -1 || index === nums.length) {
    return [0, 0];
  }
  return [1, nums[index]];
}
function compare(nums, index1, index2) {
  const num1 = get(nums, index1);
  const num2 = get(nums, index2);
  if (num1[0] !== num2[0]) {
    return num1[0] > num2[0] ? 1 : -1;
  }
  if (num1[1] === num2[1]) {
    return 0;
  }
  return num1[1] > num2[1] ? 1 : -1;
}
function findPeakElement(nums) {
  const length = nums.length;
  let left = 0;
  let right = length - 1;
  let result = -1;
  while (left <= right) {
    const middle = (left + right) >> 1;
    if (
      compare(nums, middle - 1, middle) < 0 &&
      compare(nums, middle, middle + 1) > 0
    ) {
      result = middle;
      break;
    }
    if (compare(nums, middle, middle + 1) < 0) {
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }
  return result;
}