LeetCode如何寻找峰值

峰值是什么

在LeetCode中，峰值被定义为一个数组中的一个元素，大于其相邻元素。换句话说，如果一个数组nums满足nums[i] > nums[i-1] && nums[i] > nums[i+1]，那么nums[i]就是一个峰值。

暴力解法

暴力解法是一种简单但效率较低的寻找峰值的方法。遍历整个数组nums，对于每一个元素nums[i]，判断其是否是峰值。为了避免数组越界，需要特殊处理数组的两个边界元素。暴力解法的详细步骤如下：

1. 遍历数组nums，对于每一个下标i：
2. 如果i等于0，则只需要判断nums[0]是否大于nums[1]即可。
3. 如果i等于nums的长度减1，则只需要判断nums[length-1]是否大于nums[length-2]即可。
4. 对于其他情况，判断nums[i]是否大于nums[i-1]和nums[i+1]。
5. 如果nums[i]是峰值，返回nums[i]。
6. 如果整个数组中没有峰值，返回-1。

1|public int findPeakElement(int[] nums) {

 2|    int length = nums.length;

 3|    for (int i = 0; i < length; i++) {

 4|        if (i == 0) {

 5|            if (length == 1 || nums[i] > nums[i+1]) {

 6|                return nums[i];

 7|            }

 8|        } else if (i == length - 1) {

 9|            if (nums[i] > nums[i-1]) {

10|                return nums[i];

11|            }

12|        } else {

13|            if (nums[i] > nums[i-1] && nums[i] > nums[i+1]) {

14|                return nums[i];

15|            }

16|        }

17|    }

18|    return -1;

19|}

二分查找法

二分查找法是一种高效的寻找峰值的方法。它利用了峰值的定义，通过不断缩小搜索范围来快速找到一个峰值。

二分查找法的思路如下：

1. 定义left和right分别指向数组nums的首尾元素。
2. 不断计算mid = (left + right) / 2，判断nums[mid]与其相邻元素的大小关系。
3. 如果nums[mid] < nums[mid+1]，说明峰值在mid的右侧，将left移动到mid+1。
4. 如果nums[mid] >= nums[mid+1]，说明峰值在mid的左侧或就是mid，将right移动到mid。
5. 重复步骤2到步骤4，直到left = right，此时指向的元素就是峰值。

1|public int findPeakElement(int[] nums) {

 2|    int left = 0;

 3|    int right = nums.length - 1;

 4|    while (left < right) {

 5|        int mid = (left + right) / 2;

 6|        if (nums[mid] < nums[mid+1]) {

 7|            left = mid + 1;

 8|        } else {

 9|            right = mid;

10|        }

11|    }

12|    return left;

13|}

以上是两种常用的方法，暴力解法的时间复杂度为O(n)，其中n为数组长度；二分查找法的时间复杂度为O(log(n))。在LeetCode中寻找峰值问题中，可以使用这两种方法来快速找到峰值。