162. Find Peak Element

题目

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [1,2,3,1]

Output: 2

Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]

Output: 5

Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

题目大意

峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到一个峰值元素并返回其索引。数组可能包含多个峰值，返回任何一个即可。

你可以假设 nums[-1] = nums[n] = -∞，注意这里 n 是数组的长度。算法的时间复杂度需要达到 O(log n)。

解题思路

峰值元素的定义是值大于左右相邻元素的元素，且数组边界外的元素视为负无穷。这意味着数组的第一个元素若大于第二个元素，则它是峰值；最后一个元素若大于倒数第二个元素，也是峰值。
题目允许返回任意一个峰值，且要求时间复杂度为 O(log n)，因此二分查找是最优选择。
二分查找的核心逻辑：对于中间元素 nums[mid]，如果它小于右侧元素 nums[mid+1]，说明右侧一定存在峰值（因为数组向右递增，最终会遇到边界的负无穷）；否则，左侧（包括当前元素）一定存在峰值。
该思路无需处理复杂的边界条件，通过不断缩小搜索范围，最终总能找到一个峰值。

方法一：暴力解法

思路

遍历数组中的每个元素，逐个检查是否为峰值。
对于第一个元素，只需判断是否大于第二个元素；对于最后一个元素，只需判断是否大于倒数第二个元素；对于中间元素，需同时大于左右两个相邻元素。
找到第一个满足条件的元素即返回其索引。

复杂度分析

时间复杂度：O(n)，需要遍历数组中的所有元素。
空间复杂度：O(1)，仅使用常数级额外空间。
局限性：虽然实现简单，但时间复杂度不符合 O(log n) 的要求，适用于理解峰值的基本概念，但不适用于大数据量场景。

方法二：二分查找法（最优解）

思路

利用二分查找的特性，通过比较中间元素与右侧元素的大小来缩小搜索范围：
- 若 nums[mid] < nums[mid+1]：说明峰值在右侧，将左边界移至 mid+1。
- 否则：说明峰值在左侧（包括当前元素），将右边界移至 mid。
- 重复上述过程，直到左右边界重合，此时的索引即为峰值索引。
边界处理：由于题目假设数组边界外为负无穷，无需额外判断边界元素的特殊情况，二分查找的逻辑自然包含了对边界峰值的检测。

复杂度分析

时间复杂度：O(log n)，每次迭代将搜索范围缩小一半。
空间复杂度：O(1)，仅使用常数级额外空间。
优势：高效处理大数据量，完全满足题目对时间复杂度的要求，且逻辑简洁，无需复杂的条件判断。

代码实现

int findPeakElement(int* nums, int numsSize) {
    if (numsSize == 1) return 0;
    if (numsSize == 2) return nums[0] > nums[1] ? 0 : 1;
    
    for (int i = 0; i < numsSize; i++) {
        if (i == 0) {
            // 第一个元素只需大于第二个元素
            if (nums[i] > nums[i + 1]) {
                return i;
            }
        } else if (i == numsSize - 1) {
            // 最后一个元素只需大于倒数第二个元素
            if (nums[i] > nums[i - 1]) {
                return i;
            }
        } else {
            // 中间元素需同时大于左右元素
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                return i;
            }
        }
    }
    // 理论上不会走到这里，因题目保证至少有一个峰值
    return -1;
}

int findPeakElement(int* nums, int numsSize) {
    if (numsSize == 1) return 0; // 单个元素本身就是峰值
    int left = 0, right = numsSize - 1;
    
    while (left < right) {
        int mid = left + (right - left) / 2; // 避免溢出的中间值计算
        if (nums[mid] < nums[mid + 1]) {
            // 右侧存在峰值，移动左边界
            left = mid + 1;
        } else {
            // 左侧存在峰值，移动右边界
            right = mid;
        }
    }
    return left; // 循环结束时left == right，即为峰值索引
}

代码解析

暴力解法：通过遍历数组，逐个判断元素是否符合峰值条件。虽然直观，但时间复杂度较高，不适用于大规模数据。
二分查找法：利用二分查找的高效性，通过比较中间元素与右侧元素的大小，不断缩小搜索范围。最终收敛的索引一定是峰值，时间复杂度为 O(log n)，完全满足题目要求。该方法无需复杂的边界判断，逻辑简洁且高效。

关键注意点

二分查找中 mid 的计算使用 left + (right - left) / 2 而非 (left + right) / 2，避免了整数溢出的风险。
对于严格递增的数组，最后一个元素会被判定为峰值；对于严格递减的数组，第一个元素会被判定为峰值，均符合题目逻辑。
当数组存在多个峰值时，算法返回其中任意一个，符合题目要求。