162. 寻找峰值
题目描述
如果一个元素严格大于它左右两边的邻居，就称它为峰值。
输入整数数组 nums，相邻两个元素一定不相等。把数组两端之外都看作负无穷，即 nums[-1] = nums[n] = -∞。
找出任意一个峰值，返回它的下标（从 0 开始）。有多个峰值时，返回哪一个都可以。算法时间复杂度必须为 O(log n)。
输入：nums = [1,2,3,1] 输出：2
解释：nums[2] = 3 比两侧的 2 和 1 都大，是峰值。
输入：nums = [1,2,1,3,5,6,4] 输出：5
解释：nums[5] = 6 大于两侧的 5 和 4，是峰值。下标 1 处的 2 也是峰值，返回 1 同样正确。
数据范围
1 <= nums.length <= 1000-2^31 <= nums[i] <= 2^31 - 1- 对每个合法的
i，nums[i] != nums[i + 1]。
解题思路：二分查找（爬坡）
比较 nums[mid] 和右邻 nums[mid+1]。若 nums[mid] > nums[mid+1]，说明在下坡，左侧（含 mid）一定有峰：从 mid 往左走，要么一直上升到 nums[-1]=-∞ 前的第一个元素，要么中途遇到下降，都会形成峰，故 hi = mid。否则在上坡，右侧（不含 mid）一定有峰，lo = mid + 1。
为什么正确
[lo, hi] 内一定存在峰值：nums[lo-1] < nums[lo]（或 lo=0），且 nums[hi] > nums[hi+1]（或 hi=n-1）。
复杂度分析
时间 O(log n)，空间 O(1)。
易错点
用 lo <= hi 加 mid+1 容易越界；不要比较 nums[mid-1]，否则 mid=0 时越界。二分不要求整体有序，只要能判断哪一半一定有解。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[mid + 1]:
hi = mid
else:
lo = mid + 1
return loclass Solution {
public int findPeakElement(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (nums[mid] > nums[mid + 1]) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
}class Solution {
public:
int findPeakElement(vector<int>& nums) {
int lo = 0, hi = nums.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (nums[mid] > nums[mid + 1]) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
};func findPeakElement(nums []int) int {
lo, hi := 0, len(nums)-1
for lo < hi {
mid := (lo + hi) / 2
if nums[mid] > nums[mid+1] {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}var findPeakElement = function(nums) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] > nums[mid + 1]) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};function findPeakElement(nums: number[]): number {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] > nums[mid + 1]) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}其他解法
线性扫描沿着上坡一步步走到第一个峰值；二分查找每次根据坡向丢掉一半区间，把时间降到 O(log n)。
解法 2：线性扫描 时间 O(n)，空间 O(1)
从左到右找第一个满足 nums[i] > nums[i+1] 的下标 i，返回它。因为 nums[-1] 视为负无穷，并且在 i 之前序列一直上升，所以 nums[i] 大于两侧。找不到时整个数组递增，返回最后一个下标。
代码最简单，便于理解“上坡一定能走到峰值”。时间是 O(n)，不满足题目要求的 O(log n)。
from typing import List
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
return i
return len(nums) - 1class Solution {
public int findPeakElement(int[] nums) {
int n = nums.length;
for (int i = 0; i + 1 < n; i++) {
if (nums[i] > nums[i + 1]) return i;
}
return n - 1;
}
}class Solution {
public:
int findPeakElement(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i + 1 < n; i++) {
if (nums[i] > nums[i + 1]) return i;
}
return n - 1;
}
};func findPeakElement(nums []int) int {
n := len(nums)
for i := 0; i+1 < n; i++ {
if nums[i] > nums[i+1] {
return i
}
}
return n - 1
}var findPeakElement = function(nums) {
const n = nums.length;
for (let i = 0; i + 1 < n; i++) {
if (nums[i] > nums[i + 1]) return i;
}
return n - 1;
};function findPeakElement(nums: number[]): number {
const n = nums.length;
for (let i = 0; i + 1 < n; i++) {
if (nums[i] > nums[i + 1]) return i;
}
return n - 1;
};