162. Find Peak Element

Posted on | In
Words count in article: 413 | Reading time ≈ 1

题目

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞。

示例 1:

1
2
3
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

示例 2：

1
2
3
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 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.

说明：

  • 你的解法应该是 O(logN) 时间复杂度的。

解法

解法一：

遍历一趟，遇到nums[i] > nums[i + 1]就返回当前的i

Java

1
2
3
4
5
6
7
8
public int findPeakElement(int[] nums) {
		for (int i = 0;i < nums.length - 1;i++) {
			if (nums[i] > nums[i + 1]) {
				return i;
			}
		}
		return nums.length - 1;
    }

解法二：

二分查找。

根据得到的中点位置mid，判断后续是在左半部分还是右半部分搜索。比如：

数组：1，2，3，4，5，4，5，6，7。假设 mid = 4, mid + 1 = 5. 此时mid刚好是第一个峰值，那么就可以继续在左半部分搜索。

数组：1，2，3，4，5，4，5，6，7。假设 mid=3，mid + 1 = 4. 此时还没到右半部分，说明要继续在右半部分搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int findPeakElement(int[] nums) {
		return search(nums, 0, nums.length - 1);
    }
	
	
	private int search(int[] nums, int begin, int end) {
		if (begin == end) {
			return begin;
		}
		
		int mid = (begin + end) / 2;
		if (nums[mid] > nums[mid + 1]) {
			return search(nums, 0, mid);
		} else {
			return search(nums, mid + 1, end);
		}
	}
0%