LeetCode 第162题：寻找峰值

题目描述

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞，并且对于所有有效的 i 都有 nums[i] != nums[i + 1]。换句话说，相邻元素的值都不相等。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 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
-2^31 <= nums[i] <= 2^31 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]

解题思路

方法：二分查找

由于要求时间复杂度为O(log n)，自然想到二分查找。关键是如何确定搜索方向。关键点：

如果中间元素比右侧元素小，说明右侧一定有峰值，向右搜索
如果中间元素比右侧元素大，说明左侧一定有峰值（可能是中间元素本身），向左搜索
由于题目保证了相邻元素不相等，所以不会有平坦的情况

时间复杂度：O(log n)，其中n是数组长度。空间复杂度：O(1)，只使用常数额外空间。

代码实现

C# 实现

public class Solution {
    public int FindPeakElement(int[] nums) {
        int left = 0;
        int right = nums.Length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) {
                // 峰值在右侧
                left = mid + 1;
            } else {
                // 峰值在左侧（包括mid）
                right = mid;
            }
        }
        
        return left; // 或者return right，此时left == right
    }
}

Python 实现

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < nums[mid + 1]:
                # 峰值在右侧
                left = mid + 1
            else:
                # 峰值在左侧（包括mid）
                right = mid
                
        return left  # 或者return right，此时left == right

C++ 实现

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) {
                // 峰值在右侧
                left = mid + 1;
            } else {
                // 峰值在左侧（包括mid）
                right = mid;
            }
        }
        
        return left; // 或者return right，此时left == right
    }
};

性能分析

各语言实现的性能对比：

实现语言	执行用时	内存消耗	特点
C#	92 ms	38.2 MB	实现简洁，性能适中
Python	36 ms	15.1 MB	代码最简洁
C++	4 ms	8.8 MB	性能最优