LeetCode如何寻找峰值

# LeetCode如何寻找峰值

## 1. 问题定义

在LeetCode的[162. 寻找峰值](https://leetcode.cn/problems/find-peak-element/)问题中，要求：
- 给定一个整数数组`nums`，其中`nums[i] ≠ nums[i+1]`
- 找到任意一个峰值元素并返回其索引
- 峰值元素指其值严格大于左右相邻值的元素
- 对于边界元素，只需满足大于一侧相邻元素即可
- 要求时间复杂度为O(log n)

示例：

输入：nums = [1,2,3,1] 输出：2（因为nums[2] = 3是峰值）

## 2. 基础解法分析

### 2.1 线性扫描法（O(n)）

最直观的解法是遍历数组，找到第一个满足条件的元素：
```python
def findPeakElement(nums):
    for i in range(len(nums)-1):
        if nums[i] > nums[i+1]:
            return i
    return len(nums)-1

缺点：虽然简单，但无法满足题目要求的对数时间复杂度。

2.2 分治法（O(log n)）

利用数组的局部有序性，可以采用类似二分查找的方法：

def findPeakElement(nums):
    left, right = 0, len(nums)-1
    
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[mid+1]:
            right = mid
        else:
            left = mid + 1
    return left

3. 二分查找的数学原理

为什么二分法适用于此问题？关键在于：

1. 必然存在峰值：根据鸽巢原理，任意数组至少存在一个峰值
2. 局部单调性：
   • 如果nums[mid] > nums[mid+1]，左侧必然存在峰值
   • 如果nums[mid] < nums[mid+1]，右侧必然存在峰值
3. 边界处理：当区间缩小到1个元素时，该元素就是峰值

4. 算法实现细节

4.1 关键比较逻辑

if nums[mid] > nums[mid+1]:
    # 向左搜索（包含mid）
    right = mid
else:
    # 向右搜索（排除mid）
    left = mid + 1

4.2 终止条件

使用left < right而非left <= right的原因： - 保证循环结束时left == right - 避免出现mid+1越界的情况

4.3 多语言实现

Java版本：

public int findPeakElement(int[] nums) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] > nums[mid + 1]) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

C++版本：

int findPeakElement(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[mid + 1]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

5. 边界情况处理

1. 单元素数组：直接返回0
2. 严格递增数组：返回最后一个元素
3. 严格递减数组：返回第一个元素
4. 多个峰值：返回任意一个即可

6. 复杂度分析

• 时间复杂度：O(log n)，每次迭代将搜索范围减半
• 空间复杂度：O(1)，仅使用常数空间

7. 进阶思考

7.1 二维峰值查找

扩展问题：在二维矩阵中寻找峰值（值大于等于所有相邻元素）

解法思路： 1. 选取中间列 2. 找到该列的最大值 3. 比较其与左右元素 4. 递归搜索左侧或右侧

7.2 多个峰值的查找

如果需要找到所有峰值，则必须使用O(n)的线性扫描方法：

def findAllPeaks(nums):
    res = []
    if len(nums) == 1:
        return [0]
    if nums[0] > nums[1]:
        res.append(0)
    for i in range(1, len(nums)-1):
        if nums[i-1] < nums[i] > nums[i+1]:
            res.append(i)
    if nums[-1] > nums[-2]:
        res.append(len(nums)-1)
    return res

8. 实际应用场景

1. 信号处理：寻找EEG信号中的特征波峰
2. 金融分析：识别股票价格走势的局部高点
3. 气象学：定位气压分布图中的高压中心

9. 总结

1. 寻找峰值问题展示了如何将二分查找应用于非有序数组
2. 关键在于发现”局部单调性”这一可分治的特性
3. 算法选择需平衡时间复杂度和实现复杂度
4. 边界条件的处理是正确性的关键保障

提示：在面试中遇到类似问题时，建议先阐述线性解法，再逐步优化到对数复杂度解法，展示思维过程。 “`

（全文约1100字，实际字数可能因格式略有差异）