一、题目描述

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

  • arr.length >= 3
  • 存在 i0 < 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 = [0,2,1,0]
输出:1

示例 3:

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

示例 4:

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

提示

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

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

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 山脉数组的峰顶索引( LeetCode 852 ):https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/
class Solution {
    public int peakIndexInMountainArray(int[] arr) {

        // 题目告诉我们 3 <= arr.length <= 10^4
        // 也就是说 arr 的最左侧和最右侧肯定不是山峰

        // 所以如果存在山脉,数组中最左侧的元素肯定不是山脉的山峰位置,因为它的左侧没有元素了
        // 因此,搜索区间需要从索引为 1 的位置开始
        int left = 1;

        // 同样的,如果存在山脉,数组中最右侧的元素肯定不是山脉的山峰位置,因为它的右侧没有元素了
        // 因此,搜索区间需要从索引为 nums.length - 2 的位置结束
        int right = arr.length - 2;

        // 在 while 循环里面,left 不断的 ++,而 right 不断的 --
        // 当 left 和 right 相等, [ left , right ] 这个区间存在一个元素的时候
        // 这也意味着这个区间里面的元素找不到其它元素和它进行比较,它已经傲视群峰,就是山脉,得到结果
        // 所以,当 left == right 时,跳出循环
        // 此时,while 循环的判断不可以可以使用等号
        while(left < right) {

            // left + (right - left) / 2 和 (left + right) / 2 的结果相同
            // 但是使用 left + (right - left) / 2 可以防止由于 left 、right 同时太大,导致相加的结果溢出的问题
            // 比如数据 int 的最大值为 2,147,483,647
            // 此时,left 为 2,147,483,640
            // 此时,right 为 2,147,483,646
            // 两者直接相加超过了 2,147,483,647,产生了溢出
            int mid = left + (right - left) / 2;

            // 由于题目中提示【题目数据保证 arr 是一个山脉数组】
            // 所以对于 arr 中任意位置的元素,比如 mid 所在的位置,只有以下三种情况

            // 1、mid 处于山峰位置,也就是它的值大于左侧,也大于右侧
            // arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1] 
            // 此时,找到了结果
            if( arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]  ){

                // 返回结果
                return mid;

            }

            // 2、mid 处于上升状态,也就是它的值大于左侧,同时小于右侧
            // arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1]
            // 那么,我们需要在右侧区间去寻找出下降的那段     
            if( arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1]){

                // 缩小区间,从 [ mid + 1 , right ] 里面去找
                left = mid + 1;

            }

            // 3、mid 处于下降状态,也就是它的值小于左侧,同时小于右侧
            // arr[mid] < arr[mid - 1] && arr[mid] > arr[mid + 1]
            // 那么,我们需要在左侧区间去寻找出上升的那段     
            if( arr[mid] < arr[mid - 1] && arr[mid] > arr[mid + 1]  ){

                // 缩小区间,从 [ left , mid - 1 ] 里面去找
                right = mid - 1;

            } 

        }

        // 跳出循环,此时 left == right,区间为 [ left,right ],只有一个元素
        // 这也意味着这个区间里面的元素找不到其它元素和它进行比较,它已经傲视群峰,就是山脉,得到结果
        // 返回这个下标即可
        return left;
    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 山脉数组的峰顶索引( LeetCode 852 ):https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {

        // 题目告诉我们 3 <= arr.length <= 10^4
        // 也就是说 arr 的最左侧和最右侧肯定不是山峰

        // 所以如果存在山脉,数组中最左侧的元素肯定不是山脉的山峰位置,因为它的左侧没有元素了
        // 因此,搜索区间需要从索引为 1 的位置开始
        int left = 1;

        // 同样的,如果存在山脉,数组中最右侧的元素肯定不是山脉的山峰位置,因为它的右侧没有元素了
        // 因此,搜索区间需要从索引为 nums.length - 2 的位置结束
        int right = arr.size() - 2;

        // 在 while 循环里面,left 不断的 ++,而 right 不断的 --
        // 当 left 和 right 相等, [ left , right ] 这个区间存在一个元素的时候
        // 这也意味着这个区间里面的元素找不到其它元素和它进行比较,它已经傲视群峰,就是山脉,得到结果
        // 所以,当 left == right 时,跳出循环
        // 此时,while 循环的判断不可以可以使用等号
        while(left < right) {

            // left + (right - left) / 2 和 (left + right) / 2 的结果相同
            // 但是使用 left + (right - left) / 2 可以防止由于 left 、right 同时太大,导致相加的结果溢出的问题
            // 比如数据 int 的最大值为 2,147,483,647
            // 此时,left 为 2,147,483,640
            // 此时,right 为 2,147,483,646
            // 两者直接相加超过了 2,147,483,647,产生了溢出
            int mid = left + (right - left) / 2;

            // 由于题目中提示【题目数据保证 arr 是一个山脉数组】
            // 所以对于 arr 中任意位置的元素,比如 mid 所在的位置,只有以下三种情况

            // 1、mid 处于山峰位置,也就是它的值大于左侧,也大于右侧
            // arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1] 
            // 此时,找到了结果
            if( arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]  ){

                // 返回结果
                return mid;

            }

            // 2、mid 处于上升状态,也就是它的值大于左侧,同时小于右侧
            // arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1]
            // 那么,我们需要在右侧区间去寻找出下降的那段     
            if( arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1]){

                // 缩小区间,从 [ mid + 1 , right ] 里面去找
                left = mid + 1;

            }

            // 3、mid 处于下降状态,也就是它的值小于左侧,同时小于右侧
            // arr[mid] < arr[mid - 1] && arr[mid] > arr[mid + 1]
            // 那么,我们需要在左侧区间去寻找出上升的那段     
            if( arr[mid] < arr[mid - 1] && arr[mid] > arr[mid + 1]  ){

                // 缩小区间,从 [ left , mid - 1 ] 里面去找
                right = mid - 1;

            } 

        }

        // 跳出循环,此时 left == right,区间为 [ left,right ],只有一个元素
        // 这也意味着这个区间里面的元素找不到其它元素和它进行比较,它已经傲视群峰,就是山脉,得到结果
        // 返回这个下标即可
        return left;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 山脉数组的峰顶索引( LeetCode 852 ):https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/
class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:

        # 题目告诉我们 3 <= arr.length <= 10^4
        # 也就是说 arr 的最左侧和最右侧肯定不是山峰

        # 所以如果存在山脉,数组中最左侧的元素肯定不是山脉的山峰位置,因为它的左侧没有元素了
        # 因此,搜索区间需要从索引为 1 的位置开始
        left = 1

        # 同样的,如果存在山脉,数组中最右侧的元素肯定不是山脉的山峰位置,因为它的右侧没有元素了
        # 因此,搜索区间需要从索引为 nums.length - 2 的位置结束
        right = len(arr) - 2

        # 在 while 循环里面,left 不断的 ++,而 right 不断的 --
        # 当 left 和 right 相等, [ left , right ] 这个区间存在一个元素的时候
        # 这也意味着这个区间里面的元素找不到其它元素和它进行比较,它已经傲视群峰,就是山脉,得到结果
        # 所以,当 left == right 时,跳出循环
        # 此时,while 循环的判断不可以可以使用等号
        while left < right : 

            # left + (right - left) / 2 和 (left + right) / 2 的结果相同
            # 但是使用 left + (right - left) / 2 可以防止由于 left 、right 同时太大,导致相加的结果溢出的问题
            # 比如数据 int 的最大值为 2,147,483,647
            # 此时,left 为 2,147,483,640
            # 此时,right 为 2,147,483,646
            # 两者直接相加超过了 2,147,483,647,产生了溢出
            mid = left + (right - left) // 2

            # 由于题目中提示【题目数据保证 arr 是一个山脉数组】
            # 所以对于 arr 中任意位置的元素,比如 mid 所在的位置,只有以下三种情况

            # 1、mid 处于山峰位置,也就是它的值大于左侧,也大于右侧
            # arr[mid] > arr[mid + 1] and arr[mid] > arr[mid - 1] 
            # 此时,找到了结果
            if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid + 1]  :

                # 返回结果
                return mid


            # 2、mid 处于上升状态,也就是它的值大于左侧,同时小于右侧
            # arr[mid] > arr[mid - 1] and arr[mid] < arr[mid + 1]
            # 那么,我们需要在右侧区间去寻找出下降的那段     
            if arr[mid] > arr[mid - 1] and arr[mid] < arr[mid + 1] :

                # 缩小区间,从 [ mid + 1 , right ] 里面去找
                left = mid + 1


            # 3、mid 处于下降状态,也就是它的值小于左侧,同时小于右侧
            # arr[mid] < arr[mid - 1] and arr[mid] > arr[mid + 1]
            # 那么,我们需要在左侧区间去寻找出上升的那段     
            if arr[mid] < arr[mid - 1] and arr[mid] > arr[mid + 1]   :

                # 缩小区间,从 [ left , mid - 1 ] 里面去找
                right = mid - 1


        # 跳出循环,此时 left == right,区间为 [ left,right ],只有一个元素
        # 这也意味着这个区间里面的元素找不到其它元素和它进行比较,它已经傲视群峰,就是山脉,得到结果
        # 返回这个下标即可
        return left

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注