1. 寻找峰值

162. 寻找峰值 - 力扣（LeetCode）

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 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]

1.1 题目解析

目标：在“严格先升后降”的山脉数组中找到唯一峰顶下标 i，满足
arr[0] < … < arr[i-1] < arr[i] > arr[i+1] > … > arr[n-1]。
关键结构（可二分的二段性）：定义性质 P(k) := arr[k] > arr[k-1]（是否还在上坡）。在区间 k ∈ [1, n-2] 上，P(k) 呈先真后假：峰顶及其左侧为真，峰顶右侧为假。因此问题等价于：在 [1, n-2] 中找“最后一个使 P(k) 为真”的位置 → 即峰顶。
搜索区间：为避免越界并且不丢解，取 [1, n-2]（峰不在两端，且要访问 k-1）。
收敛策略：配合“上中位数”与单侧保留（上坡保留 mid），保证每轮缩小区间，最终 left == right。
复杂度：时间 O(log n)，空间 O(1)。

1.2 解法

i）对 P(k) := arr[k] > arr[k-1] 做“最后一个真”的二分查找

ii）若 arr[mid] > arr[mid-1]（上坡/在峰左侧或即将到峰），峰一定在 [mid, right]，令 left = mid（保留 mid）。

iii）否则（下坡），峰一定在 [left, mid-1]，令 right = mid - 1。

iiii）用上中位数避免死循环；终止时 left == right 即峰顶。

正确性要点：

不变量：每轮后峰顶始终在 [left, right]。
收敛性：上中位数 + 上坡时 left = mid 保证区间严格缩小。
复杂度：O(log n) / O(1)。

1.3 代码实现

class Solution {public int peakIndexInMountainArray(int[] arr) {int left = 1, right = arr.length - 2; // 峰不在两端，且要用到 mid-1while (left < right) {int mid = left + (right - left + 1) / 2; // 上中位数if (arr[mid] > arr[mid - 1]) {left = mid;          // 上坡：峰在 [mid, right]} else {right = mid - 1;     // 下坡：峰在 [left, mid-1]}}return left; // 即峰顶索引}
}

2. 山脉数组

852. 山脉数组的峰顶索引 - 力扣（LeetCode）

给定一个长度为 n 的整数山脉数组 arr ，其中的值递增到一个 峰值元素 然后递减。

返回峰值元素的下标。

你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

示例 1：

输入：arr = [0,1,0]
输出：1

示例 2：

输入：arr = [0,2,1,0]
输出：1

示例 3：

输入：arr = [0,10,5,2]
输出：1

提示：

3 <= arr.length <= 105
0 <= arr[i] <= 106
题目数据保证 arr 是一个山脉数组

2.1 题目解析

目标：在“严格先升后降”的数组（山脉数组）里找到峰顶下标 i，满足 arr[0] < ... < arr[i-1] < arr[i] > arr[i+1] > ... > arr[n-1]。峰值不在两端，且一定唯一。
本质：这是在上升段与下降段的分界点上找位置。设性质 P(k) := arr[k] > arr[k-1]（“还在上坡”）。在山脉数组中：：
- 峰顶及其左侧：P(k) 恒为真（还在上坡或刚到顶的左侧观察点）。
- 峰顶右侧：P(k) 恒为假（已经下坡）。因而在区间 k ∈ [1, n-1]，P(k) 呈现先真后假的“二段性”。我们要找的就是“最后一个使 P(k) 为真”的 k，它正是峰顶索引。
为何能用二分：有了“先真后假”的结构，就能用二分在 P(k) 上做“找最后一个真”。这比线性扫描把复杂度从 O(n) 降到 O(log n)。
边界与越界：为了比较 arr[mid] 与 arr[mid-1]，mid 最小得是 1；又因为峰不在两端，最大可到 n-2。所以把搜索区间定为 [1, n-2]，既不丢解也不越界。
三种位置类型与判断：
从“趋势”角度看，mid 可能在：
1. 上升段：arr[mid] > arr[mid-1]（继续上坡）
2. 下降段：arr[mid] < arr[mid-1]（已下坡）
3. 峰顶：满足 arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1] 实际实现里只用“与左邻比较”也足够：峰顶在“与左邻比较为真”的那一段的最右端，所以按“找最后一个真”就能把指针收敛到峰顶；无需显式判断右邻。

2.2 解法

i）在闭区间 left = 1, right = n-2 上二分（峰不在两端，且我们要用到 arr[mid-1]）。

ii）取上中位数：mid = left + (right - left + 1) / 2。

iii）若 arr[mid] > arr[mid - 1]（仍在上坡），则峰一定在 [mid, right]，令 left = mid。

iiii）否则（已在下坡），峰一定在 [left, mid - 1]，令 right = mid - 1。

iiiii）直到 left == right，即为峰顶索引，返回之。

正确性要点

不变量：峰顶始终在 [left, right]。
- 上坡保留 [mid, right] 不丢峰；
- 下坡保留 [left, mid-1] 不丢峰。
收敛性：选“上中位数”并在上坡时赋 left = mid，保证区间严格缩小，终将 left == right。
复杂度：时间 O(log n)，空间 O(1)。

2.3 代码实现

class Solution {public int peakIndexInMountainArray(int[] arr) {int n = arr.length;int left = 1, right = n - 2; // 峰不在两端，且需访问 arr[mid-1]while (left < right) {int mid = left + (right - left + 1) / 2; // 上中位数if (arr[mid] > arr[mid - 1]) {// 上坡：峰在 [mid, right]，保留 midleft = mid;} else {// 下坡：峰在 [left, mid-1]，丢弃 midright = mid - 1;}}return left; // 或 right}
}