# 852 Peak Index in a Mountain Array

Binary search 算完記得是 end = mid - 1/start = mid + 1,因為 mid 在上一輪就被計算過了不是答案

LeetCode

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

學到什麼

找對方法解就會變好順,這邊記得 Binary Search 一次算完是

end = mid - 1;  // 因為 mid 已經在上一次被計算過了不是答案
start = mid + 1;

Last updated