852. Peak Index in a Mountain Array

題目描述

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 a mountain array arr, return the index i such that arr[0] < arr[1] < … < arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1].

You must solve it in O(log(arr.length)) time complexity.

範例

Example 1:

Input: arr = [0,1,0]
Output: 1

Example 2:

Input: arr = [0,2,1,0]
Output: 1

Example 3:

Input: arr = [0,10,5,2]
Output: 1

Constraints:

• 3 <= arr.length <= 10⁵
• 0 <= arr[i] <= 10⁶
• arr is guaranteed to be a mountain array.

解答

C++

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        return binarySearch(arr);
    }

    int binarySearch(vector<int>& arr) {
        int left = 0, right = arr.size();

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
            // printf("left=%d\tright=%d\tmid=%d\n", left, right, mid);
        }
        return left;
    }
};

Step by Step 的講解

Jerry Wu25 July, 2023

Javascript

function peakIndexInMountainArray(arr) {
  let min = 0;
  let max = arr.length - 1;

  while (max > min) {
    const mid = (min + max) >> 1;
    if (arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1]) return mid;
    if (arr[mid] > arr[mid - 1]) {
      min = mid + 1;
    } else {
      max = mid;
    }
  }
}

幾個月沒做binary search的題目而已…又因為邊界條件錯了兩次…
Marsgoat25 July, 2023

function peakIndexInMountainArray(arr) {
  let min = 0;
  let max = arr.length - 1;

  while (max > min) {
    const mid = (min + max) >> 1;
    if (arr[mid] < arr[mid + 1]) {
      min = mid + 1;
    } else {
      max = mid;
    }
  }

  return min;
}

把if (arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1])這段判斷拿掉了，多此一舉，最後return min就好了，不用每次都判斷反而慢
Marsgoat25 July, 2023

TypeScript

function peakIndexInMountainArray(arr: number[]): number {
  const binarySearch = (arr: number[], start: number, end: number): number => {
    if (start >= end - 1) {
      return arr[start] > arr[end] ? start : end;
    }

    const mid = (end + start) >> 1;
    const midEl = arr[mid];

    if (midEl > arr[mid - 1] && midEl > arr[mid + 1]) {
      return mid;
    } else if (midEl < arr[mid - 1]) {
      return binarySearch(arr, start, mid);
    } else {
      return binarySearch(arr, mid, end);
    }
  };

  return binarySearch(arr, 0, arr.length - 1);
}

Sheep26 July, 2023

Reference

回到題目列表