【LeetCode】每日一题 2023_12_18 寻找峰值 (二分)

2023-12-18 09:42:15

刷题前唠嗑


LeetCode?启动!!!

题目:寻找峰值

题目链接:162. 寻找峰值

题目描述

代码与解题思路

func findPeakElement(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left+(right-left)/2
        if nums[mid] < nums[mid+1] {
            left = mid+1
        } else if nums[mid] > nums[mid+1] {
            right = mid
        }
    }
    return right
}

乍一看,我们好像无从下手,那就慢慢分析,看看该怎么解决。

题目要求我们要查找数组中任意一个峰值,那我们可以怎么找到峰值呢?我们可以分析到,其实这个数组无非就分为连个区间,一个是递增区间,一个是递减区间,而峰值就是两个区间交替的标志

假设我们随机找一个点,如果他比右边位置的值小,那就证明他在一个递增的区间;如果他比右边的位置的值大,那就证明他在一个递减的区间

通过这个性质,我们使用二分算法,当 nums[mid] < nums[mid+1] 时,在一个递增的区间,山顶必定在 mid+1 以及之后的位置;当 nums[mid] > nums[mid+1] 时,在一个递减的区间,山顶则可能在 mid 或者是之前的位置(这里要注意了,山顶有可能就是 mid 位置)

所以 right = mid,而不需要 -1 的操作。也因为这里不需要 -1,当 left == right 的时候,如果我们已经找到山顶了,那该怎么跳出循环?

这里我们可以选择特判一下,也可以使用 left < right 作为循环条件
————————————————
版权声明:本文为CSDN博主「戊子仲秋」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/Locky136/article/details/133382439

结语

之前写过这篇文章的题解,这下可以自己引用自己了,真好玩,嘿嘿

文章来源:https://blog.csdn.net/Locky136/article/details/135054253
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。