Let's call an array A a mountain if the following properties hold:
A.length >= 3
There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].
input: 一組 Array
output: 找到最大值的 index
Example 1:
Input: [0,1,0]
Output: 1
Example 2:
Input: [0,2,1,0]
Output: 1
Note:
3 <= A.length <= 10000
0 <= A[i] <= 10^6
A is a mountain, as defined above.
/**
* @param {number[]} A
* @return {number}
*/
var peakIndexInMountainArray = function(A) {
};
Edge Case
會不會有兩個答案，例如 [ 0, 1, 2, 2, 0 ]
如何解
想到 Binary search，從中間切，以 [0, 6, 5, 4, 3] 為例
左 > 自己 > 右，往左找
左 < 自己 < 右，往右找
左 < 自己 > 右，找到囉
var peakIndexInMountainArray = function(A) {
let start = 0;
let end = A.length - 1;
let mid;
while(end >= start){
mid = Math.floor((start + end) / 2);
if(A[mid - 1] > A[mid] && A[mid] > A[mid + 1]){
end = mid - 1;
}else if(A[mid - 1] < A[mid] && A[mid] < A[mid + 1]){
start = mid + 1;
}else{
return mid;
}
}
};
console.log(peakIndexInMountainArray([3, 4, 5, 1]))
// faster than 99.28% of JavaScript online submissions