寻找峰值

怎样从“无序数组 nums=[1,2,3,1]，找任一峰值下标（严格大于左右邻居；边界外视为 -∞）。”推导出 坡度二分 · 山脉折线，并证明每次状态变化都不会漏掉答案？

中心结论：数组看成山脉折线。只比较 nums[mid] 与 nums[mid+1]：上坡则峰在右（lo=mid+1），否则峰在左含 mid（hi=mid）。循环 lo<hi 防 mid+1 越界。

峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你可以假设 nums[-1] = nums[n] = -∞。

你的解法应该是 O(logN) 时间复杂度的。

在本站主例中，无序数组 nums=[1,2,3,1]，找任一峰值下标（严格大于左右邻居；边界外视为 -∞）。

算法最终需要得到或观察：下标 2 值 3 是峰值；时间 O(log n)，空间 O(1)。

线性扫描没有利用判定条件的单调性；二分每次用一个判断安全排除一半候选。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“有序区间闸门”，明确答案需要观察什么。
2. 2状态只维护 lo/hi/mid、坡度方向、区间 [lo,hi] 至少含一峰。
3. 3转移每一步按照 数组看成山脉折线。只比较 nums[mid] 与 nums[mid+1]：上坡则峰在右（lo=mid+1），否则峰在左含 mid（hi=mid）。循环 lo<hi 防 mid+1 越界。
4. 4收尾读取 下标 2 值 3 是峰值；时间 O(log n)，空间 O(1)。，并复核边界与复杂度。

二分的核心不是 mid 公式，而是左右哪一侧可以被证明不含答案。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：lo/hi/mid、坡度方向、区间 [lo,hi] 至少含一峰。

给出一个数组，数组里面存在多个“山峰”，(山峰的定义是，下标 `i` 比 `i-1`、`i+1` 位置上的元素都要大)，找到这个“山峰”，并输出其中一个山峰的下标。 这一题是第 852 题的伪加强版，第 852 题中只存在一个山峰，这一题存在多个山峰。但是实际上搜索的代码是一样的，因为此题只要求随便输出一个山峰的下标即可。思路同第 852 题。

数组看成山脉折线。只比较 nums[mid] 与 nums[mid+1]：上坡则峰在右（lo=mid+1），否则峰在左含 mid（hi=mid）。循环 lo<hi 防 mid+1 越界。

执行过程中持续维护：lo/hi/mid、坡度方向、区间 [lo,hi] 至少含一峰。

正确性依赖以下不变量：[lo, hi] 区间内始终至少存在一个峰值（边界 nums[-1]、nums[n] 视为 -∞）。

面试时可以压缩为：这题不是找最大值，也不是有序数组二分。我们利用峰值一定存在，以及局部坡度判断方向。若 nums[mid] < nums[mid+1]，说明右侧沿上坡方向一定能遇到峰；否则左侧含 mid 一定有峰。每次缩小一半区间，时间 O(log n)，空间 O(1)。

落到当前题，执行机制可以压缩为：数组看成山脉折线。只比较 nums[mid] 与 nums[mid+1]：上坡则峰在右（lo=mid+1），否则峰在左含 mid（hi=mid）。循环 lo<hi 防 mid+1 越界。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入无序数组 nums=[1,2,3,1]，找任一峰值下标（严格大于左右邻居；边界外视为 -∞）。 因为：数组看成山脉折线。只比较 nums[mid] 与 nums[mid+1]：上坡则峰在右（lo=mid+1），否则峰在左含 mid（hi=mid）。循环 lo<hi 防 mid+1 越界。
2. 2候选区间 = 整个数组把整个有序数组作为初始候选区间。 因为：数组有序是二分的前提:看一眼 mid 就能判断答案在左还是右。
3. 3看 mid=1,a[mid]=2取区间中点 mid,比较 a[mid] 与 target。 因为：a[mid] 偏小,答案只可能在右半。
4. 4丢弃左半,lo = mid+1把 mid 及其左侧全部排除。 因为：有序数组里 mid 左侧都 ≤ a[mid] < target,不可能是答案。
5. 5预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
6. 6看 mid=2,a[mid]=3取区间中点 mid,比较 a[mid] 与 target。 因为：正好相等,mid 就是答案。
7. 7命中,返回下标 2a[mid] 等于 target,直接返回下标。 因为：二分每一步都不丢弃可能含答案的一侧,命中即正确。
8. 8收尾与复杂度下标 2 值 3 是峰值；时间 O(log n)，空间 O(1)。 因为：时间 O(log n) · 空间 O(1)。数组看成山脉折线。只比较 nums[mid] 与 nums[mid+1]：上坡则峰在右（lo=mid+1），否则峰在左含 mid（hi=mid）。循环 lo<hi 防 mid+1 越界。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// 解法一 二分
func findPeakElement(nums []int) int {
	if len(nums) == 0 || len(nums) == 1 {
		return 0
	}
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)>>1
		if (mid == len(nums)-1 && nums[mid-1] < nums[mid]) || (mid > 0 && nums[mid-1] < nums[mid] && (mid <= len(nums)-2 && nums[mid+1] < nums[mid])) || (mid == 0 && nums[1] < nums[0]) {
			return mid
		}
		if mid > 0 && nums[mid-1] < nums[mid] {
			low = mid + 1
		}
		if mid > 0 && nums[mid-1] > nums[mid] {
			high = mid - 1
		}
		if mid == low {
			low++
		}
		if mid == high {
			high--
		}
	}
	return -1
}

// 解法二 二分
func findPeakElement1(nums []int) int {
	low, high := 0, len(nums)-1
	for low < high {
		mid := low + (high-low)>>1
		// 如果 mid 较大，则左侧存在峰值，high = m，如果 mid + 1 较大，则右侧存在峰值，low = mid + 1
		if nums[mid] > nums[mid+1] {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}

func main() {
    // 1. 主例
    //    输入：mode="classic", array=[1,2,3,1], target=3
    //    期望：下标 2 值 3 是峰值；时间 O(log n)，空间 O(1)。
    //
    // 2. 失败 / 未命中
    //    检查：循环必须是 lo<hi 而非 lo<=hi：循环内访问 nums[mid+1]，lo==hi 时会越界。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC153 旋转最小；LC852 山脉峰
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意无序数组 nums=[1,2,3,1]，找任一峰值下标（严格大于左右邻居；边界外视为 -∞）。
2. 2重复线性扫描没有利用判定条件的单调性；二分每次用一个判断安全排除一半候选。
3. 3优化数组看成山脉折线。只比较 nums[mid] 与 nums[mid+1]：上坡则峰在右（lo=mid+1），否则峰在左含 mid（hi=mid）。循环 lo<hi 防 mid+1 越界。
4. 4证明[lo, hi] 区间内始终至少存在一个峰值（边界 nums[-1]、nums[n] 视为 -∞）。
5. 5复杂度时间 O(log n)，空间 O(1)