0%

### 题目描述

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` 往后遍历的第一个不是比后面元素大的即为局部峰值（注意：这里可以这么判断是因为题目给定了前后两个元素不能相等

• 时间复杂度: `O(log n)`
• 空间复杂度: `O(1)`

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

GitHub: Leetcode-C++-Solution