题解 | 寻找峰值

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    int findPeakElement(vector<int>& nums) {
        // write code here
        int left = 0;
        int right = nums.size() - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            // 如果中间元素大于右侧元素，峰值在左侧（包括mid)(mid高,峰值在包括高的一侧)
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            }
            // 如果中间元素小于右侧元素，峰值在右侧(mid低,故不包括mid)
            else {
                left = mid + 1;
            }
        }

        // 当left == right时，找到峰值
        return left;
    }
};

这个问题可以使用二分查找在 O(logN) 时间内解决。关键观察点是：由于数组两端的边界被视为负无穷，且相邻元素不相等，所以数组中至少存在一个峰值。

方法思路
问题分析：我们需要找到一个严格大于其左右相邻元素的峰值。由于数组边界被视为负无穷，且相邻元素不相等，所以峰值一定存在。

算法选择：使用二分查找。比较中间元素与其右侧元素：
如果中间元素大于右侧元素，说明峰值在左侧（包括中间元素）
如果中间元素小于右侧元素，说明峰值在右侧

复杂度分析：时间复杂度为 O(logN)，空间复杂度为 O(1)。