题目：
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 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
- -231 <= nums[i] <= 231 - 1
- 对于所有有效的 i 都有 nums[i] != nums[i + 1]
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-peak-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
一、【二分查找-爬坡法】
分析：
- 题目中的条件是：nums[-1] = nums[n] = -∞，说明数组中一定是从小到大再到小的过程，这其中一定存在峰值，有可能只有一个；
- 看到要求时间复杂度为O(log n) ，可以初步想到用二分查找；
- 二分查找：找到中点所在地方，中点可能是某座山的山峰，山的下坡处，山的上坡处，如果是山峰，最后二分终止也会找到，问题关键在于二分方向，并不知道山峰在我们左边还是右边。核心在于：爬坡，如果你往下坡方向走，也许可能遇到新的山峰，但是也许是一个一直下降的坡，最后到边界。但是如果你往上坡方向走，就算最后到上边界，由于最边界是负无穷，所以也一定能找到山峰。总之，往递增的方向上，二分，一定能找到，往递减的方向只是可能找到，也许没有。 二分：初始化左右边界left = 0, right = nums.length - 1，计算出mid，循环条件：left < right，比较nums[mid] 和 nums[mid +1]：
- nums[mid] < nums[mid + 1]：说明mid右边是上坡，mid不是峰值且右边肯定存在峰值，继续往右查找，即left = mid + 1；
- nums[mid] >= nums[mid + 1]：说明mid右边是下坡，这可能遇到山峰，也可能遇不到，为了保险起见，不往右边找了，缩小范围往左边找，但是mid有可能就是一个峰值，即right = mid;
- 循环结束的条件：left == right，区间缩小到一个点，肯定left或者right为峰值，返回一个即可。
java代码（left < right）：
1 class Solution {
2 public int findPeakElement(int[] nums) {
3 int left = 0, right = nums.length - 1;
4 while (left < right){
5 int mid = left + (right - left) / 2;
6 //mid右边是在上坡，右边存在峰值
7 if (nums[mid] < nums[mid + 1]){
8 left = mid + 1;
9 }else{
10 //nums[mid] >= nums[mid+1]
11 //右边是在下坡，左边一定存在峰值，mid有可能就是峰值
12 right = mid;
13 }
14 }
15 //循环结束的条件是：left == right
16 return left;
17 }
18 }
pyhon3代码（left <= right）:
三种情况：
- mid大于它两边元素，这时mid就为一个峰值直接返回即可;
- nums[mid] < nums[mid + 1]，mid右侧在爬坡，且mid+1可能就为一个峰值，此时向右调整搜索范围，在 [mid + 1, right]范围内继续查找，即left = mid + 1;
- nums[mid] < nums[mid - 1]，mid左侧大，向左调整搜索范围，且mid-1可能为一个峰值，在 [left, mid -1]范围内继续查找，即right = mid - 1。
注意细节的处理：由于nums[-1]和nums[n]为负无穷，所以如果nums[-1]>nums[0] > nums[1]，0也是一个峰值直接返回。同样，如果 nums[n-2]< nums[n-1] < nums[n]，n-1也是一个峰值直接返回即可。
1 class Solution: 2 def findPeakElement(self, nums: List[int]) -> int: 3 n = len(nums) 4 if n == 1: 5 return 0 6 # 2个特例 7 # nums[-1]和nums[n]为负无穷 8 # 故下面两种情况可以直接返回答案 9 if nums[0] > nums[1]: 10 return 0 11 if nums[n-2] < nums[n-1]: 12 return n-1 13 left, right = 0, n - 1 14 while left <= right: 15 mid = left + (right - left) // 2 16 # mid右边上坡 17 if mid < n - 1 and nums[mid] < nums[mid + 1]: 18 left = mid + 1 19 elif mid >= 1 and nums[mid] < nums[mid - 1]: 20 # mid左边在上坡 21 right = mid - 1 22 elif mid >= 1 and mid < n - 1 and nums[mid] > nums[mid - 1] and nums[mid] > nums[mid + 1]: 23 return mid 24 return -1
二、【暴力求解】-找最大值
由于题目保证了 nums[i] != nums[i+1]，故数组nums 中最大值两侧的元素一定严格小于最大值本身。因此，最大值所在的位置就是一个峰值位置。于是对数组 nums 进行一次遍历，找到最大值对应的位置进行返回即可。
java代码：
1 class Solution {
2 public int findPeakElement(int[] nums) {
3 int ans = 0;
4 for (int i = 0; i < nums.length; i++){
5 if (nums[i] > nums[ans]){
6 ans = i;
7 }
8 }
9 return ans;
10 }
11 }
