05 August 2008
A peak element is an element that is greater than its neighbors.
Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that nums[-1] = nums[n] = -∞.
Example 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.
Example 2:
1
2
3
4
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.
这道题是求数组的一个峰值，这个峰值可以是局部的最大值，这里用遍历整个数组找最大值肯定会出现Time Limit Exceeded，比O(n)更加优化的自然就是O(logn)了，所以考虑使用类似于二分查找法来缩短时间，由于只是需要找到任意一个峰值，那么在确定二分查找折半后中间那个元素后，和紧跟的那个元素（右边）比较下大小，如果大于右边的数，则说明峰值在左边，如果小于则在右边。这样就可以至少找到一个峰值了，Time：O(logn), Space：O(1)。。
另外一种更简单的解法：由于题目中说明了局部峰值是存在的，那么实际上可以从第二个数字开始往后遍历，如果第二个数字比第一个数字小，说明此时第一个数字就是一个局部峰值；否则就往后继续遍历，现在是个递增趋势，如果此时某个数字小于前面那个数字，说明前面数字就是一个局部峰值，返回位置即可。如果循环结束了，说明原数组是个递增数组，返回最后一个位置即可，这是最坏结果，Time：O(n), Space：O(1)。
二分法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int findPeakElement(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int left = 0, right = nums.length - 1;
//这个模板保证left和right绝不会相遇，所以如果只有1个或2个元素的情况下，不会进入while循环引起mid-1越界
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid - 1]) { //左边的数较小，起码可以舍掉左边的部分，至少有个peak在现在mid或右边
left = mid;
} else {// 同样右边的数较小，舍掉右边的
right = mid;
}
}
// 同样需要比较left和right哪个大
return nums[left] > nums[right] ? left : right;
}
}
老式写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int findPeakElement(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {//先比较右边不会越界
right = mid;//在左边，有可能是mid自己
} else {
left = mid + 1;//如果是小于，不会是mid自己，所以mid+1
}
}
return right;//从0开始计算index，最后一轮是right < left跳出
}
}
从第二个数字开始找
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int findPeakElement(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
for (int index = 1; index < nums.length; index++) {
if (nums[index] < nums[index - 1]) {
return index - 1;
}
}
return nums.length - 1;//递增序列是最坏情况
}
}