【算法面试必刷Java版十九】寻找峰值

盲目刷题，浪费大量时间，博主这里推荐一个面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101

🏄🏻作者简介：CSDN博客专家，华为云云享专家，阿里云专家博主，疯狂coding的普通码农一枚

    

🚴🏻‍♂️个人主页：莫逸风

    

👨🏻‍💻专栏题目地址👉🏻牛客网面试必刷TOP101👈🏻

    

🇨🇳喜欢文章欢迎大家👍🏻点赞🙏🏻关注⭐️收藏📄评论↗️转发

题目：寻找峰值

描述：

给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。

1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于

2.假设 nums[-1] = nums[n] = −∞

3.对于所有有效的 i 都有 nums[i] != nums[i + 1]

4.你可以使用O(logN)的时间复杂度实现此问题吗？

数据范围：

1≤nums.length≤2×10⁵

−2³¹<=nums[i]<=2³¹−1

如输入[2,4,1,2,7,8,4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰。

思路一：迭代（常规）

注意审题：nums[-1]=nums[n]= -∞

1. 处理边界问题，当数组长度为1时，即为峰值，当下标0大于下标1位置时，下标0为峰值，当下标n-1大于下标n-2时，下标n-1为波峰。
2. 迭代剩余节点，当值大于前后节点时，即为山峰。

思路二：二分查找（符合O(logN)时间复杂度）

注意审题：nums[-1]=nums[n]= -∞

巧妙利用二分查找

1. 创建下标标记数组首尾，start，end。
2. 计算中间位置，如果中间位置小于左边，证明左边存在波峰，如果中间位置小于右边，证明右边存在波峰。

代码：

public int findPeakElement(int[] nums) {// write code here// 边界处理if (nums.length == 1 || nums[0] > nums[1]) return 0;if (nums[nums.length - 1] > nums[nums.length - 2]) return nums.length - 1;for (int i = 1; i < nums.length - 1; i++) {if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) return i;}return 0;
}public int findPeakElement2(int[] nums) {int left = 0;int right = nums.length - 1;while(left < right){ //二分法int mid = (left + right) / 2;if(nums[mid] > nums[mid + 1])right = mid;elseleft = mid + 1;}return right; 
}

推荐牛客网面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！