[Leetcode]162. Find Peak Element(C++)

题目描述

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

Given an 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] = -∞`.

例子

例子 1

Input: `nums = [1,2,3,1]` Output: `2` Explanation: `3 is a peak element and your function should return the index number 2.`

例子 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.`

Could you implement a solution with logarithmic complexity?

Constraints

• `1 <= nums.length <= 1000`
• `-2^31 <= nums[i] <= 2^31 - 1`
• `nums[i] != nums[i + 1]` for all valid i.

解题思路

• `nums[Mid] > nums[Mid + 1]`，此时对数组后半段 `[Mid, N - 1]` 有几种可能：
• 单调递减，这种情况下，`nums[N-1]` 是峰值，因为题目假定 `nums[N] = nums[-1] = -Inf`
• 非单调递减，那么至少会有一个峰值，因为 `nums[Mid] > nums[Mid + 1]`，从 `Mid + 1` 往后遍历的第一个不是比后面元素大的即为局部峰值（注意：这里可以这么判断是因为题目给定了前后两个元素不能相等

``````class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};
``````
• 时间复杂度: `O(log n)`
• 空间复杂度: `O(1)`

GitHub 代码同步地址： 162.FindPeakElement.cpp

Built with Hugo
Theme Stack designed by Jimmy