当前位置: 面试刷题>> 寻找峰值(经典算法150题)


题目描述

寻找峰值

在一个整数数组中,每个元素都严格大于它左边和右边的相邻元素(如果存在的话),则称该元素是一个峰值。给定一个整数数组 nums,请编写一个函数来找到数组中的一个峰值元素。你可以假设 nums[-1] = nums[n] = -∞(即数组两端的元素比数组中的任何元素都要小),这意味着数组至少存在一个峰值。

示例

输入: [1, 2, 1, 3, 5, 6, 4] 输出: 5 解释: 数组 [1, 2, 1, 3, 5, 6, 4] 中,元素 5 是一个峰值,因为它大于左右两边的元素。

PHP 示例代码

function findPeakElement($nums) {
    $left = 0;
    $right = count($nums) - 1;
    
    while ($left < $right) {
        $mid = $left + floor(($right - $left) / 2);
        
        if ($nums[$mid] < $nums[$mid + 1]) {
            // 峰值在右侧
            $left = $mid + 1;
        } else {
            // 峰值在左侧或就是当前mid
            $right = $mid;
        }
    }
    
    // 当left == right时,循环结束,left/right指向的就是峰值
    return $nums[$left];
}

// 测试
$nums = [1, 2, 1, 3, 5, 6, 4];
echo findPeakElement($nums); // 输出: 5

Python 示例代码

def findPeakElement(nums):
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = (left + right) // 2
        
        if nums[mid] < nums[mid + 1]:
            # 峰值在右侧
            left = mid + 1
        else:
            # 峰值在左侧或就是当前mid
            right = mid
    
    # left == right 时,循环结束,left/right指向的就是峰值
    return nums[left]

# 测试
nums = [1, 2, 1, 3, 5, 6, 4]
print(findPeakElement(nums))  # 输出: 5

JavaScript 示例代码

function findPeakElement(nums) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        
        if (nums[mid] < nums[mid + 1]) {
            // 峰值在右侧
            left = mid + 1;
        } else {
            // 峰值在左侧或就是当前mid
            right = mid;
        }
    }
    
    // left == right 时,循环结束,left/right指向的就是峰值
    return nums[left];
}

// 测试
let nums = [1, 2, 1, 3, 5, 6, 4];
console.log(findPeakElement(nums)); // 输出: 5

以上代码示例均采用了二分查找的思想来寻找峰值,通过不断缩小搜索范围,最终找到峰值元素。这种方法的时间复杂度为 O(log n),其中 n 是数组的长度。

推荐面试题