題目網址：https://leetcode.cn/problems/peak-index-in-a-mountain-array/

題意：如果以下屬性成立，我們就稱 arr 為山。

  • arr.length >= 3
  • arr[0] < arr[1] < ... arr[i-1] < arr[i]
  • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

找到 arr 的山峰 idx = i, 滿足arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Solution：

想法：利用 Binary Search, 不斷找中點, 並和後面一數比較, 判斷要往左邊還右邊來縮小範圍

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0, right = arr.size();

        while (left < right) {
            const int mid = left + (right - left) / 2;

            if (arr[mid] <= arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
};
  • time：$O(log(n))$ ➔ Binary Search
  • space：$O(1)$ ➔ 只需常數空間