题解 | #寻找峰值#

ChatGPT 这骚操作真的有效

好的，这里用图解和步骤详细说明如何使用二分查找法来找到数组中的峰值元素。峰值定义为：在一个元素比左右相邻元素大的情况下，这个元素就是峰值。如果元素在边界，我们只需要比较它和它的一个邻居。

思路：

1. 使用二分查找法来减少时间复杂度，通过每次对比中间元素和其右侧元素的大小来确定峰值的方向。
2. 如果 nums[mid] > nums[mid + 1]，说明峰值在左侧，包括 mid 本身。
3. 如果 nums[mid] < nums[mid + 1]，说明峰值在右侧。

图解步骤：

假设输入数组为 [1, 2, 3, 1]。我们可以分步找出峰值：

第一步：初始化指针

• 定义 left = 0，right = 3 （数组的首尾下标）。
• 计算 mid = left + (right - left) / 2 = 1。

数组： [1, 2, 3, 1]
索引：  0  1  2  3
指针：  L     M     R

• 中间元素 nums[mid] = 2。
• 检查 nums[mid] 和 nums[mid + 1]：2 < 3。

结果：因为 nums[mid] < nums[mid + 1]，峰值在右侧，所以我们更新 left = mid + 1 = 2。

第二步：缩小范围继续查找

• 现在 left = 2，right = 3。
• 重新计算 mid = left + (right - left) / 2 = 2。

数组： [1, 2, 3, 1]
索引：     L M    R

• 此时 nums[mid] = 3。
• 检查 nums[mid] 和 nums[mid + 1]：3 > 1。

结果：因为 nums[mid] > nums[mid + 1]，峰值在左侧或中间，更新 right = mid = 2。

第三步：指针收敛

• 现在 left = 2，right = 2，即 left 和 right 重合。

数组： [1, 2, 3, 1]
索引：        L/R

• left 和 right 相等时，表示找到了峰值，返回 left 或 right，结果为 2，即 nums[2] = 3 是一个峰值。

总结过程

每次比较 nums[mid] 和 nums[mid + 1]，从而确定峰值所在的方向，逐步缩小范围，直至 left 和 right 重合，指向峰值元素。

动画图示（步步缩小范围）

[1, 2, 3, 1]             -> 初始范围
 L     M     R
 
      ↓
      
[1, 2, 3, 1]             -> 缩小范围
     L/M   R
 
      ↓
      
[1, 2, 3, 1]             -> 最后范围
        L/R

代码实现

public class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        // 二分查找
        while (left < right) {
            int mid = left + (right - left) / 2;

            // 比较中间值和其右侧元素
            if (nums[mid] > nums[mid + 1]) {
                // 峰值在左侧或当前中间位置是峰值
                right = mid;
            } else {
                // 峰值在右侧
                left = mid + 1;
            }
        }
        
        // 最终 left 和 right 会收敛到峰值位置
        return left;
    }
}

这个方法通过二分查找，在每次查找时将范围缩小一半，直到锁定峰值位置，时间复杂度为 O(log n)。