题解 | #寻找峰值#

问题描述

想象你站在一条山路上，这条路从左到右有很多高低起伏的地方。你的任务是找到一个“山顶”，也就是一个地方的高度比它左边和右边都要高。如果有多座“山”，找到任何一个山顶的位置就可以。

示例

• 输入：[2, 4, 1, 2, 7, 8, 4]
• 输出：1 或 5
• 说明：4 和 8 都是峰值元素，返回 4 的索引 1 或者 8 的索引 5 都可以。
• 输入：[1, 2, 3, 1]
• 输出：2
• 说明：3 是峰值元素，返回其索引 2。

解释

1. 准备阶段：
1. 把这条路分成两段：左边一段和右边一段。
2. 最开始，左边段包含起点，右边段包含终点。
2. 查找过程：
1. 找到中间的位置。
2. 如果中间位置的高度比它左边和右边都要高，那就是一个“山顶”了。
3. 如果中间位置的高度比左边低，说明山顶可能在左边段。
4. 如果中间位置的高度比右边低，说明山顶可能在右边段。
5. 重复上面的步骤，直到找到山顶。
3. 结束：
1. 如果找到了“山顶”，就告诉别人它的位置。

具体步骤

假设我们要找的数组是 [2, 4, 1, 2, 7, 8, 4]：

1. 准备阶段：
1. 左边段包含 2，右边段包含 4。
2. 查找过程：
1. 中间位置的数字是 4（位置 1）。
2. 4 比左边的 2 和右边的 1 都要高，所以 4 是一个“山顶”。
3. 结束：
1. 我们找到了 “山顶”，位置是 1。

Java 实现

下面是具体的 Java 代码实现：

public class PeakFinder {

    // 查找峰值元素
    public static 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; // 在右边段继续找
            }
        }

        return left; // 返回找到的峰值位置
    }

}

示例1

输入：[2, 4, 1, 2, 7, 8, 4]

• 输出：1 或 5
• 说明：4 和 8 都是峰值元素，返回 4 的索引 1 或者 8 的索引 5 都可以。

示例2

输入：[1, 2, 3, 1]

• 输出：2
• 说明：3 是峰值元素，返回其索引 2。

如果这篇文章对你有帮助，请点个免费的赞👍，让它帮助更多的人。