题目描述(中等难度)

162. Find Peak Element - 图1

给一个数组,找出任意一个峰顶。找出的这个峰顶的特点就是,比它的左邻居和右邻居都大。

解法一 线性扫描

因为 nums[-1] 看做负无穷,所以从第 0 个元素开始,它一定是上升的趋势,由于我们要找峰顶,所以当它第一次出现下降,下降前的值就是我们要找的了。

如果它一直上升到最后一个值,又因为 nums[n] 看做负无穷,所以最后一个值就可以看做一个峰顶。

  1. public int findPeakElement(int[] nums) {
  2. for (int i = 0; i < nums.length - 1; i++) {
  3. //第一次下降
  4. if (nums[i] > nums[i + 1]) {
  5. return i;
  6. }
  7. }
  8. //一直上升
  9. return nums.length - 1;
  10. }

解法二 二分法

要不是题目下边提示时间复杂度可以达到 log 级别,还真不敢往二分的方面想。因为二分法,我们一般用在有序数组上,那么这个题为什么可以用二分呢?

不管什么情况,之所以能用二分,是因为我们可以根据某个条件,直接抛弃一半的元素,从而使得时间复杂度降到 log 级别。

至于这道题,因为题目告诉我们可以返回数组中的任意一个峰顶。所以我们只要确定某一半至少存在一个峰顶,那么另一半就可以抛弃掉。

我们只需要把 nums[mid]nums[mid + 1] 比较。

先考虑第一次二分的时候,start = 0end = nums.length - 1

如果 nums[mid] < nums[mid + 1],此时在上升阶段,因为 nums[n] 看做负无穷,也就是最终一定会下降,所以 mid + 1end 之间至少会存在一个峰顶,可以把左半部分抛弃。

如果 nums[mid] > nums[mid + 1],此时在下降阶段,因为 nums[0] 看做负无穷,最初一定是上升阶段,所以 startmid 之间至少会存在一个峰顶,可以把右半部分抛弃。

通过上边的切割,我们就保证了后续左边界一定是在上升,右边界一定是在下降,所以第二次、第三次… 的二分就和上边一个道理了。

代码的话就可以有两种形式了,一种递归,一种迭代。

递归的代码如下:

  1. public int findPeakElement(int[] nums) {
  2. return findPeakElementHelper(nums, 0, nums.length - 1);
  3. }
  4. private int findPeakElementHelper(int[] nums, int start, int end) {
  5. if (start == end) {
  6. return start;
  7. }
  8. int mid = (start + end) >>> 1;
  9. if (nums[mid] < nums[mid + 1]) {
  10. return findPeakElementHelper(nums, mid + 1, end);
  11. } else {
  12. return findPeakElementHelper(nums, start, mid);
  13. }
  14. }

由于递归形式比较简单,所以我们最好用迭代去实现,因为递归的话需要压栈的空间。虽然上边的递归是尾递归的形式,不需要压栈,但这需要编译器的支持。

  1. public int findPeakElement(int[] nums) {
  2. int start = 0;
  3. int end = nums.length - 1;
  4. while(start!=end) {
  5. int mid = (start + end) >>> 1;
  6. if(nums[mid] < nums[mid + 1]) {
  7. start = mid + 1;
  8. }else {
  9. end = mid;
  10. }
  11. }
  12. return start;
  13. }

第一次遇到不需要有序数组也可以二分的题,蛮有意思。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话,可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法,强烈推荐一个我之前学过的课程,可以点击 这里 查看详情