符合下列属性的数组 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 ，即山峰顶部。

 

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

 

提示：

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

 

进阶：很容易想到时间复杂度 O(n) 的解决方案，你可以设计一个 O(log(n)) 的解决方案吗？

 

注意：本题与主站 852 题相同：https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/

Related Topics
  • 数组
  • 二分查找

  • 👍 15
  • 👎 0

    • 一般选手

    嗯，找峰值。
    先排除几个特殊情况

    • 数组长度只有1，直接返回0
    • 数组长度只有2，要么0下标的大要么1下标的大
    • 整个数组都是递增的，或者整个数组都是递减的，判断前两位或者后两位的大小关系，这个情况可以包含前面的情况2
    • 剩下的就是在数组中间一定有峰值的，且数组长度一定是大于2的情况，用二分法尝试寻找
      • 找到二分中间值，如果这个比左边和右边 都大，直接返回下标
      • 如果中间值和前面后面组成是递增的，则在说明峰值在后面，继续在后面的区间寻找
      • 如果中间值和前面后面组成的是递减的，则说明峰值在前面，则继续在前面的区间寻找
      • 因为给定的数组肯定只有一个峰值，所以除了上面的三种情况之外没有其他的情况了

    有兴趣的话可以看下另外一题162. 寻找峰值，很像，但是又有点不一样，这题给的数组中可能存在多个峰值。不过只要求返回一个峰值，本质上讨论的情况还是基本一样的。

    关于二分的模板和边界情况的需要多加注意

    class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        if (arr.length == 1){
            return 0;
        }
        if (arr[0] > arr[1]){
            return 0;
        }
        if (arr[arr.length-1] > arr[arr.length-2]){
            return arr.length;
        }
        int left = 0;
        int right = arr.length - 1;
        while (left < right){
            int mid = left + ( (right - left) >> 1 );
            if (arr[mid - 1] < arr[mid] &&  arr[mid + 1] < arr[mid]){
                return mid;
            }
            if (arr[mid - 1] < arr[mid] &&  arr[mid + 1] > arr[mid]){
                //上升
                left = mid+1;
            }else{
                //下降
                right = mid;
            }
        }
        return left;
    }
}

    不一般选手

    题面中提供了以下信息

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

    嗯，才这么点数据，看了下 34 个测试用例，这不简单么？直接撸一下

    class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int i = -1;
        for (; ++i < arr.length && arr[i] < arr[i+1];);
        return i;
    }
}