05 August 2008
如果以下属性成立，我们称数组 arr 为山：
arr.length >= 3
存在一些 i 与 0 < i < arr.length - 1 使得：
arr[0] < arr[1] < … arr[i-1] < arr[i]
arr[i] > arr[i+1] > … > arr[arr.length - 1]
给定一个保证为山的整数数组 arr，返回任何 i 满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr [arr.length - 1]。
两个方法
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public int peakIndexInMountainArray(int[] arr) {
// int n = arr.length;
// int first = 0;
// int sec = 1;
// int third = 2;
// ******** O(n) ********* //
/*
while(first<n && sec<n && third<n){
if(arr[first] < arr[sec] && arr[sec] > arr[third]){
return sec;
}
else{
first++;
sec++;
third++;
}
}
return sec;
*/
// ******** O(logn) ********* //
// Pattern => increasing order < peak > decreasing order
int n = arr.length;
int start = 0;
int end = arr.length-1;
int mid = start+(end-start)/2;
while(start<=end){
// As it is guranteed array is mountain
if(mid!=0 && mid!=n-1 && arr[mid]>arr[mid-1] && arr[mid]>arr[mid+1]){
return mid;
}
// increasing order
else if(arr[mid] < arr[mid+1]){
start = mid+1;
}
else{
end = mid-1;
}
mid = start+(end-start)/2;
}
return mid;
}
}