您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

BM19 寻找峰值

1、题目

2、思路

一般我们看到时间复杂的要求为log2n,我们就可以考虑使用二分查找的方式。因为题目只要求我们找打一个峰值的下标,则可以考虑使用二分,如果中间值小于右边,那么右边一定存在峰值,故可以向左边进行寻找left+1;不明白的可以看下标准的题解:

因为二分查找的本质是二段性,二分查找的过程本质是对可行区间的压缩。只要满足二段性的问题都可以用二分查找解决。在这里二段性的体现是峰值的左边单调增,右边单调减。你可能会反驳给我们的数值不只有一个峰值,但是只要我们控制好条件,一定可以把范围压缩到只有一个峰值的情况,来看看该怎么处理:

  • nums[mid] < nums[mid + 1]说明在“上坡”,则可以使left = mid + 1(因为mid肯定不是峰值),向“峰”处压缩
  • nums[mid] > nums[mid + 1]说明在“下坡”,则应该使right = mid(mid可能是峰值),往“峰”处压缩

虽然开始left和right之间可能有多个峰值,但是随着left和right不断逼近,最后两者之间一定会压缩到一个峰值上,因为两者都是向“峰”不断靠近的,但是不会超过最终的“峰”

上面分析的过程可以很轻松的使用左闭右开型二分查找实现。对左开右闭,链接左闭右开二分查找不熟的同学可以看看这篇博客【玩转二分查找Ⅰ】左闭右闭型,左开右闭型,左闭右开型(动图演绎)

3、代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int findPeakElement (int[] nums) {
        
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        while(left<right){
            mid = (left+right)/2;
            if(nums[mid]<nums[mid+1]){
                left = mid+1;
            }else if(nums[mid]>nums[mid+1]){
                right = mid;
            }
        }
        return right;
        
        
    
            
        
        
        
    }
}


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进