寻找峰值

162. 寻找峰值

leetcode 链接

思路：

1.二分查找。定义一个 get 函数，返回 nums[index]的值，其中 index 为-1 或者为 nums.length 时返回负无穷。

2.然后二分查询，找到 nums[mid] > nums[mid + 1] && nums[[mid] > nums[mid - 1]时返回 mid，否则判断 nums[mid] < nums[mid + 1]时，left = mid + 1，否则 right = mid - 1。

typescript 解法

function findPeakElement(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (
      get(nums, mid - 1) < get(nums, mid) &&
      get(nums, mid + 1) < get(nums, mid)
    ) {
      return mid;
    }
    if (get(nums, mid + 1) > get(nums, mid)) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}
function get(nums: number[], index: number): number {
  if (index === -1 || index === nums.length) {
    return -Infinity;
  }
  return nums[index];
}

go 解法

func findPeakElement(nums []int) int {
    n := len(nums)
    get := func(i int) int {
        if i == -1 || i == n {
            return math.MinInt64
        }
        return nums[i]
    }
    left, right := 0, n - 1
    for {
        mid := left + (right - left) / 2
        if get(mid - 1) < get(mid) && get(mid) > get(mid + 1) {
            return mid
        }
        if get(mid) < get(mid + 1) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}