二分与排序中等2 种解法
#162寻找峰值
返回任意一个严格大于左右相邻元素的峰值下标，数组边界外视为负无穷。
#数组#二分查找
原题
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 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[mid] 与 nums[mid + 1]：上坡时右侧必有峰值，下坡时 mid 及其左侧必有峰值。
解法 1：二分沿坡上行
保留必含峰值的一半区间，直到左右边界收敛。
-
时间复杂度： O(log n)
-
空间复杂度： O(1)
final class Solution {
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
// 循环不变量：闭区间 [left, right] 内至少存在一个峰值
while (left < right) {
int middle = left + (right - left) / 2;
// 下坡时峰值可在 middle，故保留左半区并令 right = middle
if (nums[middle] > nums[middle + 1]) right = middle;
// 上坡时 middle 不可能是峰值，安全排除到 middle + 1
else left = middle + 1;
}
return left;
}
}解法 2：寻找全局最大值
全局最大值在相邻不等的数组中一定是合法峰值。
-
时间复杂度： O(n)
-
空间复杂度： O(1)
final class Solution {
public int findPeakElement(int[] nums) {
// 以首元素为当前最大值，单元素数组也自然返回 0
int maximum = 0;
for (int i = 1; i < nums.length; i++) {
// 始终保存已扫描前缀的最大值下标
if (nums[i] > nums[maximum]) maximum = i;
}
// 全局最大值不小于任一邻居，结合相邻不等即为严格峰值
return maximum;
}
}边界与易错点
- 二分循环使用 left < right，才能安全访问 mid + 1。
- 题目保证相邻元素不相等；这是严格峰值存在性的关键。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
easy/Q162_findPeakElement.java