当前位置：首页 > article >正文

Leetcode 寻找峰值

article 2024/11/20 18:03:16

在这里插入图片描述

为了实现时间复杂度为 $O(\log n)$ ，可以使用二分查找法：

解题思路：

峰值的特性是：当前元素大于左右相邻元素。
使用二分法：
- 如果 nums[mid] > nums[mid + 1]，说明峰值在左侧或当前 mid 位置（包括 mid），因此将 right = mid。
- 否则峰值在右侧，因此将 left = mid + 1。
不断收缩区间，直到 left == right，此时即找到峰值。

时间复杂度：

时间复杂度：(O(\log n))，因为每次迭代都将搜索范围减半。
空间复杂度：(O(1))，不需要额外的空间。

java 实现

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            // 如果中点比右侧元素大，说明峰值在左侧（包括mid）
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else { // 否则峰值在右侧
                left = mid + 1;
            }
        }
        
        // 最终left和right会相遇，此时即为峰值位置
        return left;
    }
}

数组即便不是有序的，为什么仍然二分查找仍然可以找到峰值？

这是因为这道题的二分查找并不依赖于数组是否有序，而是利用了“峰值”的定义和数组的局部特性。

关键点

题目定义的峰值条件：
- 峰值是指某个元素严格大于其左右邻居的元素。
- 如果一个元素 nums[mid] > nums[mid + 1]，那么在 mid 或者其左侧一定存在一个峰值。
- 如果 nums[mid] < nums[mid + 1]，那么在 mid 的右侧一定存在一个峰值。
为什么可以二分？
二分查找的核心在于：
- 每次选择一个中间点 mid，并根据某个条件判断下一个搜索范围。
- 在这道题中，“峰值”可以通过比较 nums[mid] 和 nums[mid + 1] 来判断范围：
  - 如果 nums[mid] > nums[mid + 1]：
    - 峰值在左侧或就是 mid，因为 mid 本身比右边的大（局部性质），可以舍弃右侧部分。
  - 如果 nums[mid] < nums[mid + 1]：
    - 峰值一定在右侧，因为右边存在一个更大的值，最终会到达一个下降点形成峰值。
这利用了“递增到下降”的局部特性来缩小搜索范围。
数学直观解释：
- 假设数组中不存在连续相等的数字（即没有平缓区域），并且在数组两端可以假想有值为负无穷的元素（题目已假设 nums[-1] = nums[n] = -∞）。
- 在数组中总能找到一个峰值元素，原因是：
  - 如果数组中存在一个“上升”趋势，例如 nums[i] < nums[i+1]，那么在右侧一定有一个峰值。
  - 如果数组中存在一个“下降”趋势，例如 nums[i] > nums[i+1]，那么左侧也一定存在一个峰值。
这种趋势保证了每次二分缩小范围后，最终一定会收敛到某个峰值点。
非有序数组的适用性：
题目并没有要求数组有序。因为峰值是局部性质（仅与相邻元素有关），只需要每次确定搜索方向，而不是依赖整体有序性。二分查找法的效率仍然得以保证。

举例说明

以数组 nums = [1, 2, 1, 3, 5, 6, 4] 为例：

初始：
- left = 0, right = 6，取中间点 mid = 3，nums[mid] = 3。
- 比较 nums[mid] 和 nums[mid + 1]，3 < 5，说明右侧有峰值，更新 left = mid + 1。
第二轮：
- left = 4, right = 6，取中间点 mid = 5，nums[mid] = 6。
- 比较 nums[mid] 和 nums[mid + 1]，6 > 4，说明左侧有峰值，更新 right = mid。
第三轮：
- left = 4, right = 5，取中间点 mid = 4，nums[mid] = 5。
- 比较 nums[mid] 和 nums[mid + 1]，5 < 6，说明右侧有峰值，更新 left = mid + 1。
最终：
- left = right = 5，返回 5，此时峰值为 6。