【LeetCode(Java) - 162】寻找峰值

    科技2025-10-06  10

    文章目录

    1、题目描述2、解题思路3、解题代码

    1、题目描述

    2、解题思路

      我们可以将 nums 数组中的任何给定序列视为交替的升序和降序序列。通过利用这一点,以及“可以返回任何一个峰作为结果”的要求,我们可以利用二分查找来找到所需的峰值元素。

      在简单的二分查找中,我们处理的是一个有序数列,并通过在每一步减少搜索空间来找到所需要的数字。在本例中,我们对二分查找进行一点修改。首先从数组 nums 中找到中间的元素 mid。若该元素恰好位于降序序列或者一个局部下降坡度中(通过将 nums[i] 与右侧比较判断),则说明峰值会在本元素的左边。于是,我们将搜索空间缩小为 mid 的左边(包括其本身),并在左侧子数组上重复上述过程。

      若该元素恰好位于升序序列或者一个局部上升坡度中(通过将 nums[i] 与右侧比较判断),则说明峰值会在本元素的右边。于是,我们将搜索空间缩小为 mid 的右边,并在右侧子数组上重复上述过程。

      就这样,我们不断地缩小搜索空间,直到搜索空间中只有一个元素,该元素即为峰值元素。

      为了理解本方法的原理,让我们再次讨论前文提到的全部三种情况。

      对于 nums = {5,4,3,2,1}. 这种情况下,首先找到中间元素 3。由于它处于下降坡度,将搜索空间缩小到 [5,4,3]。对于此子数组,4 为中间元素,也处于下降坡度中,于是将搜索空间缩小到 [5,4]。现在 5 是中间元素并同样处于下降坡度,于是将搜索空间缩小到 [5]。 最终 5 作为答案被正确返回。

    3、解题代码

    class Solution { public int findPeakElement(int[] nums) { return search(nums, 0, nums.length - 1); } public int search(int[] nums, int l, int r) { if (l == r){ return l; } int mid = l + (r - l) / 2; if (nums[mid] > nums[mid + 1]){ return search(nums, l, mid); } return search(nums, mid + 1, r); } }
    Processed: 0.010, SQL: 8