LeetCode 162. Find Peak Element

题目描述

题目链接

思路

假设数组长度为N,首先判断0号位置的数和N-1位置的数是不是峰值位置。

0号位置只需要和1号位置比较,如果0号位置大,0号位置就是峰值位置。

N-1号位置只需要和N-2号位置比较,如果N-1号位置大,N-1号位置就是峰值位置。

如果0号位置和N-1在上轮比较中均是最小值,那么数组的样子必然是如下情况:

image

[0..1]区间内是增长, [N-2...N-1]区间内是下降

那么峰值位置必在[1...N-2]之间出现

此时可以通过二分来找峰值位置,先来到中点位置,假设为mid,如果:

1
arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1]

mid位置即峰值位置

否则,有如下两种情况:

情况一,趋势是:

image

则在[1...(mid-1)]区间内继续上述二分。

情况二,趋势是:

image

则在[(mid+1)...(N-2)]区间内继续上述二分。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class LeetCode_0162_FindPeakElement {

public int findPeakElement(int[] nums) {
int n = nums.length;
if (n == 1) {
return 0;
}
if (n == 2) {
return nums[0] == Math.max(nums[0], nums[1]) ? 0 : 1;
}
if (nums[n - 1] > nums[n - 2]) {
return n - 1;
}
if (nums[0] > nums[1]) {
return 0;
}
int L = 1;
int R = n - 2;
while (L <= R) {
int mid = L + ((R - L) >> 1);
if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
return mid;
} else if (nums[mid] < nums[mid + 1]) {
L = mid + 1;
} else {
R = mid - 1;
}
}
return -1;
}

}

更多

算法和数据结构笔记

参考资料