题目:
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 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 }