线性到二分，峰值查找高效法

欢迎各位小伙伴来到golang学习网，相聚于此都是缘哈哈哈！今天我给大家带来《山脉数组找峰值：线性到二分的高效方法》，这篇文章主要讲到等等知识，如果你对文章相关的知识非常感兴趣或者正在自学，都可以关注我，我会持续更新相关文章！当然，有什么建议也欢迎在评论留言提出！一起学习！

引言：山脉数组及其峰值索引

在算法领域，"山脉数组"是一种特殊的数组结构，其定义如下： 一个数组 arr 被称为山脉数组，如果满足以下条件：

1. arr.length >= 3。
2. 存在某个索引 i，满足 0 < i < arr.length - 1，使得：
   • arr[0] < arr[1] < ... < arr[i - 1] < arr[i] (数组从开头到 i 严格递增)。
   • arr[i] > arr[i + 1] > ... > arr[arr.length - 1] (数组从 i 到结尾严格递减)。

我们的目标是给定一个山脉数组 arr，返回其峰值索引 i。此外，通常要求算法的时间复杂度为 O(log(arr.length))。

方法一：线性扫描法

线性扫描法是一种直观且易于理解的解决方案。由于山脉数组只有一个峰值，且这个峰值是数组中的最大元素，我们可以通过遍历整个数组来找到这个最大值及其对应的索引。

原理

算法从数组的第一个元素开始，依次向后遍历。在遍历过程中，它会维护一个当前找到的最大值 (peakValue) 和该最大值对应的索引 (peakIndex)。每当遇到一个比 peakValue 更大的元素时，就更新 peakValue 和 peakIndex。遍历结束后，peakIndex 即为山脉数组的峰值索引。

示例代码

public class Solution {
    public static int peakIndexInMountainArray(int[] arr) {
        // 初始化峰值和峰值索引。
        // 由于题目保证arr.length >= 3，且峰值在0 < i < arr.length - 1，
        // 可以从arr[0]开始，或者确保peakValue初始值足够小。
        // 这里的实现从0开始，适用于所有非负数的情况。
        int peakValue = 0; 
        int peakIndex = 0; 

        // 遍历数组寻找最大值及其索引
        for (int i = 0; i < arr.length; i++) {
            int value = arr[i];
            if (value > peakValue) {
                peakValue = value;
                peakIndex = i;
            }
        }
        return peakIndex;
    }

    public static void main(String[] args) {
        System.out.println("示例 1: " + peakIndexInMountainArray(new int[]{0,1,2}));        // 2 (峰值是2，索引2)
        System.out.println("示例 2: " + peakIndexInMountainArray(new int[]{0,1,0}));        // 1 (峰值是1，索引1)
        System.out.println("示例 3: " + peakIndexInMountainArray(new int[]{0,2,1,0}));      // 1 (峰值是2，索引1)
        System.out.println("示例 4: " + peakIndexInMountainArray(new int[]{0,10,5,2}));     // 1 (峰值是10，索引1)
        System.out.println("示例 5: " + peakIndexInMountainArray(new int[]{0,100,500,2}));  // 2 (峰值是500，索引2)
    }
}

复杂度分析

• 时间复杂度： O(N)，其中 N 是数组的长度。算法需要遍历数组中的所有元素一次。
• 空间复杂度： O(1)，仅使用了常数额外的存储空间来保存 peakValue 和 peakIndex。

局限性

尽管线性扫描法简单直观且易于实现，但它不满足题目通常要求的 O(log(arr.length)) 时间复杂度约束。对于大型数组，其性能会随着数组长度的增加而线性下降。

方法二：二分查找法

为了满足 O(log(arr.length)) 的时间复杂度要求，我们需要利用二分查找。山脉数组的特性（先严格递增后严格递减）使其非常适合二分查找。

原理

二分查找的核心思想是每次将搜索范围减半。在山脉数组中，我们可以根据当前中间元素 arr[mid] 的值与 arr[mid+1] 的关系来判断峰值位于 mid 的哪一侧：

1. 如果 arr[mid] < arr[mid+1]： 这意味着 mid 位于山脉的上升段。峰值一定在 mid 的右侧。因此，我们将搜索范围的左边界 low 更新为 mid + 1。
2. 如果 arr[mid] > arr[mid+1]： 这意味着 mid 位于山脉的下降段，或者 mid 本身就是峰值。峰值可能在 mid 处或 mid 的左侧。因此，我们将搜索范围的右边界 high 更新为 mid。

通过不断缩小搜索范围，low 和 high 最终会汇合到峰值索引。

示例代码

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int low = 0;
        // high的初始值可以设置为arr.length - 1。
        // 根据山脉数组的定义，峰值不会是最后一个元素（arr.length - 1），
        // 且 mid + 1 在循环内部是安全的，不会越界，因为 high 最终会收敛到峰值索引，
        // 而峰值索引小于 arr.length - 1。
        int high = arr.length - 1; 

        // 当 low < high 时继续循环。
        // 最终 low 和 high 会汇合到峰值索引。
        while (low < high) {
            // 计算中间索引，防止 low + high 溢出
            int mid = low + (high - low) / 2; 

            // 如果 mid 位于上升坡 (arr[mid] < arr[mid+1])，
            // 峰值在 mid 的右侧，包括 mid+1。
            if (arr[mid] < arr[mid + 1]) {
                low = mid + 1;
            } 
            // 如果 mid 位于下降坡 (arr[mid] > arr[mid+1])，
            // 或者 mid 就是峰值。
            // 峰值在 mid 或 mid 的左侧。
            else { // arr[mid] > arr[mid + 1]
                high = mid;
            }
        }
        // 循环结束时，low（或 high，因为它们相等）即为峰值索引
        return low; 
    }
}

示例分析：arr = [0, 2, 1, 0]

1. 初始化： low = 0, high = 3
2. 第一次迭代：
   • mid = 0 + (3 - 0) / 2 = 1
   • `arr[mid] = arr

本篇关于《线性到二分，峰值查找高效法》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！