山脉数组的峰顶索引

题目

符合下列属性的数组 arr 称为山脉数组:

• arr.length >= 3
• 存在 i(0 < i < arr.length - 1) 使得:
  • arr[0] < arr[1] < ... arr[i-1] < arr[i]
  • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

给你由整数组成的山脉数组 arr, 返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i.

说明:

• 3 <= arr.length <= 10⁴
• 0 <= arr[i] <= 10⁶
• 题目数据保证 arr 是一个山脉数组

示例

输入: arr = [0, 1, 0]
输出: 1

输入: arr = [0, 2, 1, 0]
输出: 1

输入: arr = [0, 10, 5, 2]
输出: 1

输入: arr = [3, 4, 5, 1]
输出: 2

输入: arr = [24, 69, 100, 99, 79, 78, 67, 36, 26, 19]
输出: 2

题解

二分查找, 这道题要把 low 设为 1, high 设为 n - 2, 这是因为两边的数字一定不是峰顶元素. 如果 arr[mid] > arr[mid + 1], 说明 mid 右边属于下坡路部分, 所以最大数可能是 mid, 也可能落在 mid 左边.

JavaScript

/**
 * @param {number[]} arr
 * @return {number}
 */
var peakIndexInMountainArray = function (arr) {
  const n = arr.length
  let low = 1,
    high = n - 2,
    ans = 0

  while (low <= high) {
    const mid = Math.floor((low + high) / 2)

    if (arr[mid] > arr[mid + 1]) {
      ans = mid
      high = mid - 1
    } else {
      low = mid + 1
    }
  }

  return ans
}

Rust

pub fn peak_index_in_mountain_array(arr: Vec<i32>) -> i32 {
    let n = arr.len();
    let (mut low, mut high, mut ans) = (1, n - 2, 0);

    while low <= high {
        let mid = (low + high) / 2;
        if arr[mid] > arr[mid + 1] {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    ans as i32
}