题解 | #寻找峰值#

寻找峰值

https://www.nowcoder.com/practice/fcf87540c4f347bcb4cf720b5b350c76

import java.util.*;


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

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

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

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

全部评论

相关推荐

02-25 11:29
产品经理
牛客444597598号:兄弟 我只能说如果想找产品经理这种简历 基本就是毕业失业了 你这连实习都找不到的 简历跟产品经理一点都没有关系,你可以去搜搜产品的模版吧
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务