寻找峰值( LeetCode 162 )

一、题目描述

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1:

输入:nums = [1,2,3,1]
输出:2
解释:3 是峰值元素,你的函数应该返回其索引 2。

示例 2:

输入:nums = [1,2,1,3,5,6,4]
输出:1 或 5 
解释:你的函数可以返回索引 1,其峰值元素为 2;
     或者返回索引 5, 其峰值元素为 6。

提示:

  • 1 <= nums.length <= 1000
  • -2^31 <= nums[i] <= 2^31 - 1
  • 对于所有有效的 i 都有 nums[i] != nums[i + 1]

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 寻找峰值(162):https://leetcode-cn.com/problems/find-peak-element/
class Solution {
    public int findPeakElement(int[] nums) {

        // left 为当前区间最左侧的元素,可以获取到
        int left = 0;

        // right 为当前区间最右侧的元素,可以获取到
        int right = nums.length - 1;


        // 在 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;

            // 题目告诉我们 nums[-1] = nums[n] = -∞ 
            // 这暗示我们只要数组中存在一个元素比它相邻的元素大,那么沿着它一定可以找到一个峰值
            // 就像爬山一样,较小的山高度是 100,前面的山高度是 200,在前面是一个深渊,那么高度为 200 的那座山就是山峰
            // 所以比较 nums[mid] 与 nums[mid + 1] 的值

            // 如果 nums[mid] > nums[mid + 1]
            // 所以,如果存在山峰,那么这一段是右侧下降的那一段,因此需要在左侧去寻找上升的那段 
            if (nums[mid] > nums[mid + 1]) {

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

            // 如果 nums[mid] < nums[mid + 1]
            // 所以,如果存在山峰,那么这一段是左侧上升的那一段,因此需要在右侧去寻找下降的那段         
            } else {

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

            }
        }

        // 跳出循环,此时 left == right,返回这个下标即可
        return left;
    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 寻找峰值(162):https://leetcode-cn.com/problems/find-peak-element/
class Solution {
public:
    int findPeakElement(vector<int>& nums) {

        // left 为当前区间最左侧的元素,可以获取到
        int left = 0;

        // right 为当前区间最右侧的元素,可以获取到
        int right = nums.size() - 1;


        // 在 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;

            // 题目告诉我们 nums[-1] = nums[n] = -∞ 
            // 这暗示我们只要数组中存在一个元素比它相邻的元素大,那么沿着它一定可以找到一个峰值
            // 就像爬山一样,较小的山高度是 100,前面的山高度是 200,在前面是一个深渊,那么高度为 200 的那座山就是山峰
            // 所以比较 nums[mid] 与 nums[mid + 1] 的值

            // 如果 nums[mid] > nums[mid + 1]
            // 所以,如果存在山峰,那么这一段是右侧下降的那一段,因此需要在左侧去寻找上升的那段 
            if (nums[mid] > nums[mid + 1]) {

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

            // 如果 nums[mid] < nums[mid + 1]
            // 所以,如果存在山峰,那么这一段是左侧上升的那一段,因此需要在右侧去寻找下降的那段         
            } else {

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

            }
        }

        // 跳出循环,此时 left == right,返回这个下标即可
        return left;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 寻找峰值(162):https://leetcode-cn.com/problems/find-peak-element/
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:

        # left 为当前区间最左侧的元素,可以获取到
        left = 0

        # right 为当前区间最右侧的元素,可以获取到
        right = len(nums) - 1


        # 在 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 同时太大,导致相加的结果溢出的问题
            # 比如数据 的最大值为 2,147,483,647
            # 此时,left 为 2,147,483,640
            # 此时,right 为 2,147,483,646
            # 两者直接相加超过了 2,147,483,647,产生了溢出
            mid = left + (right - left) // 2

            # 题目告诉我们 nums[-1] = nums[n] = -∞ 
            # 这暗示我们只要数组中存在一个元素比它相邻的元素大,那么沿着它一定可以找到一个峰值
            # 就像爬山一样,较小的山高度是 100,前面的山高度是 200,在前面是一个深渊,那么高度为 200 的那座山就是山峰
            # 所以比较 nums[mid] 与 nums[mid + 1] 的值

            # 如果 nums[mid] > nums[mid + 1]
            # 所以,如果存在山峰,那么这一段是右侧下降的那一段,因此需要在左侧去寻找上升的那段 
            if nums[mid] > nums[mid + 1] :

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

            # 如果 nums[mid] < nums[mid + 1]
            # 所以,如果存在山峰,那么这一段是左侧上升的那一段,因此需要在右侧去寻找下降的那段         
            else :

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

        # 跳出循环,此时 left == right,返回这个下标即可
        return left

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

隐藏内容
  • 普通用户购买价格:不可购买
  • 会员用户购买价格:999积分
  • 永久会员用户购买价格:免费推荐

发表评论

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