93.寻找峰值
题目
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
- 输入：nums = [1,2,3,1]
- 输出：2
- 解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
- 输入：nums = [1,2,1,3,5,6,4]
- 输出：1 或 5
- 解释：你的函数可以返回索引 1，其峰值元素为 2； 或者返回索引 5， 其峰值元素为 6。
提示：
- 1 <= nums.length <= 1000
- -231 <= nums[i] <= 231 - 1
- 对于所有有效的 i 都有 nums[i] != nums[i + 1]
思路
峰值的定义：严格大于左右相邻的元素。
两个关键设定：
- 数组两端之外视为 -∞，即想象 nums[-1] = nums[n] = -∞。所以第一个或最后一个元素也可以是峰值。
- 题目保证 nums[i] != nums[i+1]（相邻元素不相等）。这一条是二分能成立的地基，后面会讲。
nums = [1, 2, 3, 1] → 返回 2（3 比 2 和 1 都大）
nums = [1, 2, 1, 3, 5, 6, 4] └─峰─┘ └──峰──┘ → 返回 1 或 5 都算对
"任意一个" 是本题的关键宽容度——存在多个峰值时你不需要找特定的那个。这正是 O(log n) 能做到的原因。
题目要求 O(log n)。
先解决一个认知障碍：数组无序，凭什么能二分？
二分都建立在"数组有序"上，而这题的数组完全无序，[1,2,1,3,5,6,4] 起起伏伏。
很多人会卡在这里，觉得"二分的前提被破坏了"。
真相是：二分的前提从来不是"有序"。 我在讲第 35 题时留了一句话，现在正是它兑现的时候：
▎ 二分查找的本质是「在一个单调的判定条件上找分界点」，而不是「在有序数组里找数」。
对二分来说，唯一的要求是：每次比较之后，你能确定性地扔掉一半，并且保证答案还在剩下的那一半里。
有序数组只是满足这个要求的一种情况。而本题满足它的方式是——看斜坡的方向。
核心推理：沿着上坡走，一定能撞到峰
站在中点 mid，只和它右边的邻居 mid+1 比一次：
- 情况 A：nums[mid] < nums[mid+1]（正在上坡）
？
/
/ 我在这，右边比我高
mid mid+1
断言：右半边 [mid+1, n-1] 里必然存在峰值。
为什么？从 mid+1 往右走，只有两种命运：
- 一路涨到底 → 那么最后一个元素 nums[n-1] 就是峰值（因为它右边是 -∞）
- 中途某处开始下跌 → 那个转折点就是峰值
没有第三种可能。 所以左半边（含 mid）可以整块扔掉：left = mid + 1。
- 情况 B：nums[mid] > nums[mid+1]（正在下坡）
？
\
\ 我在这，右边比我低
mid mid+1
对称地推：左半边 [left, mid] 里必然存在峰值。
从 mid 往左走，要么一路涨到 nums[left]（那 left 处就是峰，左边是 -∞），要么中途出现转折点。
注意这里 mid 本身要保留——因为 mid 完全可能就是那个峰（如果 nums[mid-1] < nums[mid]）。所以是 right = mid，不是 mid - 1。
循环不变量
把两种情况合起来，就得到了这个二分的灵魂：
▎ 区间 [left, right] 内始终至少包含一个峰值。
区间每轮折半，且不变量始终成立。当区间收缩到只剩一个元素时（left == right），这唯一的元素就必然是峰值。
这里有个很舒服的性质： 你不需要在循环里判断"找到了没有"，也不需要处理"找不到"的情况。峰值一定存在（有限数组必有最大值，最大值 必然是峰值），二分只是在把它逼出来。
相邻元素不相等，为什么是必要条件
回头看情况 A 和 B——它们穷尽了所有可能，因为 nums[mid] 和 nums[mid+1] 只能是 < 或 >。
如果允许相等，就会出现第三种情况 nums[mid] == nums[mid+1]，此时你无法判断该往哪边走：
[1, 2, 2, 2, 1] mid 落在中间那个 2 上，左右都是 2 往左找？往右找？两边都可能有峰，也可能都没有
面对平台（plateau），二分退化成必须两边都查，也就是 O(n)。所以题目那句"nums[i] != nums[i+1]"不是废话，它是算法成立的前提。
nums = [1, 2, 1, 3, 5, 6, 4]，n = 7：
┌──────┬──────┬───────┬─────┬──────────────────────────┬──────┬───────────┐ │ 轮次 │ left │ right │ mid │ nums[mid] vs nums[mid+1] │ 判断 │ 收缩 │ ├──────┼──────┼───────┼─────┼──────────────────────────┼──────┼───────────┤ │ 1 │ 0 │ 6 │ 3 │ 3 < 5 │ 上坡 │ left = 4 │ ├──────┼──────┼───────┼─────┼──────────────────────────┼──────┼───────────┤ │ 2 │ 4 │ 6 │ 5 │ 6 > 4 │ 下坡 │ right = 5 │ ├──────┼──────┼───────┼─────┼──────────────────────────┼──────┼───────────┤ │ 3 │ 4 │ 5 │ 4 │ 5 < 6 │ 上坡 │ left = 5 │ ├──────┼──────┼───────┼─────┼──────────────────────────┼──────┼───────────┤ │ — │ 5 │ 5 │ — │ 区间只剩一个 │ 退出 │ 返回 5 ✅ │ └──────┴──────┴───────┴─────┴──────────────────────────┴──────┴───────────┘
验证：nums[5] = 6，左邻 5、右邻 4，确实是峰值。
注意第 1 轮：我们扔掉了下标 0~3，其中包含了另一个峰值 1（下标 1）。这完全没问题——题目只要"任意一个"。二分放弃了一部分正确答案，换来了 O(log n) 的速度。
class Solution {
/**
* 寻找峰值 —— 在"斜坡方向"上二分
*
* 核心思想：只比较 nums[mid] 和它右边的邻居 nums[mid+1]
* nums[mid] < nums[mid+1]（上坡）→ 右半边 [mid+1, right] 必有峰值
* nums[mid] > nums[mid+1]（下坡）→ 左半边 [left, mid] 必有峰值
*
* 循环不变量：区间 [left, right] 内始终至少包含一个峰值。
* 区间每轮折半，收缩到只剩一个元素时，它就是答案。
*
* 时间复杂度 O(log n)：区间每轮减半
* 空间复杂度 O(1)
*/
fun findPeakElement(nums: IntArray): Int {
var left = 0
var right = nums.size - 1
// ⚠️ 条件是 < 而不是 <= ：
// 我们要把区间收缩到"只剩一个元素"，而不是"变成空"。
// 因为峰值一定存在，剩下的那一个就是答案。
// 另外，left == right 时 mid == left，访问 nums[mid+1] 会越界。
while (left < right) {
val mid = left + (right - left) / 2
// 因为 left < right，可推出 mid < right，所以 mid + 1 <= right，
// 永远不会越界 —— 这个安全性由循环条件保证
if (nums[mid] < nums[mid + 1]) {
// 上坡：mid 不可能是峰值（右邻比它高），答案在右边
left = mid + 1
} else {
// 下坡：mid 本身有可能就是峰值，必须保留在区间内
// ⚠️ 所以是 right = mid，绝不能写 mid - 1
right = mid
}
}
// left == right，区间只剩一个元素，由不变量保证它就是峰值
return left
}
}
复杂度
- 时间复杂度:
- 空间复杂度:
- 邮箱 ：charon.chui@gmail.com
- Good Luck!