Leetcode 852. Peak Index in a Mountain Array Binary Search

Let’s call an array arr a mountain if the following properties hold:

  • arr.length >= 3
  • There exists some i with 0 < i < arr.length - 1 such that:
    • arr[0] < arr[1] < ... arr[i-1] < arr[i]
    • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

Given an integer array arr that is guaranteed to be a mountain, return any i such that arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

Follow up: Finding the O(n) is straightforward, could you find an O(log(n)) solution?

給一個陣列arr,長度必定 >= 3,且必定為山形,也就是有一個波頂

遍尋可以找出最大值,但題目要求要O(log n)。考慮到山也有順序性(從高到低,從低到高),故使用Binary search

解題步驟

  1. 定義left, right
  2. while直到right小於等於left
  3. 找出中間點mid,假設mid>左右兩邊,則為峰頂
  4. 假設右邊比mid高,則left 設為 mid + 1
  5. 假設左邊比mid高,則right設為mid – 1
/**
 * @param {number[]} arr
 * @return {number}
 */
var peakIndexInMountainArray = function(arr) {
    let left = 0;
    let right = arr.length - 1;
    while(left <= right){
        let mid = Math.round((left + right)/2)
        if(arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1]){
            return mid;
        }else if(arr[mid] >= arr[mid-1]){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
};

Leave a Comment

發佈留言必須填寫的電子郵件地址不會公開。