LeetCode852-山脉数组的峰顶索引

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/peak-index-in-a-mountain-array/

中文链接：https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/

题目详述

我们把符合下列属性的数组 A 称作山脉：

A.length >= 3
存在 0 < i < A.length - 1 使得A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1]
给定一个确定为山脉的数组，返回任何满足 A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1] 的 i 的值。

示例 1：

1
2
输入：[0,1,0]
输出：1

示例 2：

1
2
输入：[0,2,1,0]
输出：1

提示：

  1. 3 <= A.length <= 10000
  2. 0 <= A[i] <= 10^6
  3. A 是如上定义的山脉

题目详解

  • LeetCode162-寻找峰值 与本题都是寻找峰值，区别在于前者不是山脉数组，可能存在多个峰值；后者是山脉数组，确定存在一个峰值。
  • 思路都是一致的，都是进行二分查找，两者的代码实现一致。
1
2
3
4
5
6
7
8
9
10
11
12
public class LeetCode_00852 {

    public int peakIndexInMountainArray(int[] A) {
        int l = 0, r = A.length - 1;
        while (l < r) {
            int mid = l + r >>> 1;
            if (A[mid] > A[mid + 1]) r = mid;
            else l = mid + 1;
        }
        return r;
    }
}