class Solution {
public:
int findPeakElement(vector<int>& nums) {
}
};
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 - 1i 都有 nums[i] != nums[i + 1]相似题目
原站题解
python3 解法, 执行用时: 56 ms, 内存消耗: 16.2 MB, 提交时间: 2023-12-18 00:03:24
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
left, right = -1, len(nums) - 1 # 开区间 (-1, n-1)
while left + 1 < right: # 开区间不为空
mid = (left + right) // 2
if nums[mid] > nums[mid + 1]: # 蓝色
right = mid
else: # 红色
left = mid
return right
golang 解法, 执行用时: 0 ms, 内存消耗: 2.6 MB, 提交时间: 2023-12-18 00:03:07
func findPeakElement(nums []int) int {
left, right := -1, len(nums)-1 // 开区间 (-1, n-1)
for left+1 < right { // 开区间不为空
mid := left + (right-left)/2
if nums[mid] > nums[mid+1] { // 蓝色
right = mid
} else { // 红色
left = mid
}
}
return right
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 9.1 MB, 提交时间: 2023-12-18 00:02:35
class Solution {
public:
int findPeakElement(vector<int> &nums) {
int left = -1, right = nums.size() - 1; // 开区间 (-1, n-1)
while (left + 1 < right) { // 开区间不为空
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) right = mid; // 蓝色
else left = mid; // 红色
}
return right;
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 40.6 MB, 提交时间: 2023-12-18 00:02:16
class Solution {
public int findPeakElement(int[] nums) {
int left = -1, right = nums.length - 1; // 开区间 (-1, n-1)
while (left + 1 < right) { // 开区间不为空
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) right = mid; // 蓝色
else left = mid; // 红色
}
return right;
}
}
java 解法, 执行用时: 0 ms, 内存消耗: 41.1 MB, 提交时间: 2022-12-04 14:11:50
class Solution {
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
for (; left < right; ) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
javascript 解法, 执行用时: 48 ms, 内存消耗: 41.2 MB, 提交时间: 2022-12-04 14:10:40
/**
* @param {number[]} nums
* @return {number}
*/
var findPeakElement = function(nums) {
const n = nums.length;
let left = 0, right = n - 1, ans = -1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (compare(nums, mid - 1, mid) < 0 && compare(nums, mid, mid + 1) > 0) {
ans = mid;
break;
}
if (compare(nums, mid, mid + 1) < 0) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
// 辅助函数，输入下标 i，返回一个二元组 (0/1, nums[i])
// 方便处理 nums[-1] 以及 nums[n] 的边界情况
const get = (nums, idx) => {
if (idx === -1 || idx === nums.length) {
return [0, 0];
}
return [1, nums[idx]];
}
const compare = (nums, idx1, idx2) => {
const num1 = get(nums, idx1);
const num2 = get(nums, idx2);
if (num1[0] !== num2[0]) {
return num1[0] > num2[0] ? 1 : -1;
}
if (num1[1] === num2[1]) {
return 0;
}
return num1[1] > num2[1] ? 1 : -1;
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.6 MB, 提交时间: 2022-12-04 14:10:22
func findPeakElement(nums []int) int {
n := len(nums)
// 辅助函数，输入下标 i，返回 nums[i] 的值
// 方便处理 nums[-1] 以及 nums[n] 的边界情况
get := func(i int) int {
if i == -1 || i == n {
return math.MinInt64
}
return nums[i]
}
left, right := 0, n-1
for {
mid := (left + right) / 2
if get(mid-1) < get(mid) && get(mid) > get(mid+1) {
return mid
}
if get(mid) < get(mid+1) {
left = mid + 1
} else {
right = mid - 1
}
}
}
python3 解法, 执行用时: 36 ms, 内存消耗: 15 MB, 提交时间: 2022-12-04 14:10:01
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
n = len(nums)
# 辅助函数，输入下标 i，返回 nums[i] 的值
# 方便处理 nums[-1] 以及 nums[n] 的边界情况
def get(i: int) -> int:
if i == -1 or i == n:
return float('-inf')
return nums[i]
left, right, ans = 0, n - 1, -1
while left <= right:
mid = (left + right) // 2
if get(mid - 1) < get(mid) > get(mid + 1):
ans = mid
break
if get(mid) < get(mid + 1):
left = mid + 1
else:
right = mid - 1
return ans
python3 解法, 执行用时: 36 ms, 内存消耗: 15 MB, 提交时间: 2022-12-04 14:09:15
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
n = len(nums)
idx = random.randint(0, n - 1)
# 辅助函数，输入下标 i，返回 nums[i] 的值
# 方便处理 nums[-1] 以及 nums[n] 的边界情况
def get(i: int) -> int:
if i == -1 or i == n:
return float('-inf')
return nums[i]
while not (get(idx - 1) < get(idx) > get(idx + 1)):
if get(idx) < get(idx + 1):
idx += 1
else:
idx -= 1
return idx
golang 解法, 执行用时: 4 ms, 内存消耗: 2.7 MB, 提交时间: 2022-12-04 14:09:02
func findPeakElement(nums []int) int {
n := len(nums)
idx := rand.Intn(n)
// 辅助函数，输入下标 i，返回 nums[i] 的值
// 方便处理 nums[-1] 以及 nums[n] 的边界情况
get := func(i int) int {
if i == -1 || i == n {
return math.MinInt64
}
return nums[i]
}
for !(get(idx-1) < get(idx) && get(idx) > get(idx+1)) {
if get(idx) < get(idx+1) {
idx++
} else {
idx--
}
}
return idx
}
javascript 解法, 执行用时: 60 ms, 内存消耗: 42.8 MB, 提交时间: 2022-12-04 14:08:46
/**
* @param {number[]} nums
* @return {number}
*/
var findPeakElement = function(nums) {
const n = nums.length;
let idx = parseInt(Math.random() * n);
while (!(compare(nums, idx - 1, idx) < 0 && compare(nums, idx, idx + 1) > 0)) {
if (compare(nums, idx, idx + 1) < 0) {
idx += 1;
} else {
idx -= 1;
}
}
return idx;
}
// 辅助函数，输入下标 i，返回一个二元组 (0/1, nums[i])
// 方便处理 nums[-1] 以及 nums[n] 的边界情况
const get = (nums, idx) => {
if (idx === -1 || idx === nums.length) {
return [0, 0];
}
return [1, nums[idx]];
}
const compare = (nums, idx1, idx2) => {
const num1 = get(nums, idx1);
const num2 = get(nums, idx2);
if (num1[0] !== num2[0]) {
return num1[0] > num2[0] ? 1 : -1;
}
if (num1[1] === num2[1]) {
return 0;
}
return num1[1] > num2[1] ? 1 : -1;
}
javascript 解法, 执行用时: 76 ms, 内存消耗: 41 MB, 提交时间: 2022-12-04 14:08:28
/**
* @param {number[]} nums
* @return {number}
*/
var findPeakElement = function(nums) {
let idx = 0;
for (let i = 1; i < nums.length; ++i) {
if (nums[i] > nums[idx]) {
idx = i;
}
}
return idx;
};
golang 解法, 执行用时: 4 ms, 内存消耗: 2.6 MB, 提交时间: 2022-12-04 14:07:24
func findPeakElement(nums []int) (idx int) {
for i, v := range nums {
if v > nums[idx] {
idx = i
}
}
return
}
python3 解法, 执行用时: 40 ms, 内存消耗: 15.1 MB, 提交时间: 2022-12-04 14:06:58
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
idx = 0
for i in range(1, len(nums)):
if nums[i] > nums[idx]:
idx = i
return idx