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

欢迎各位小伙伴来到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学习网公众号！