題目網址：https://leetcode.cn/problems/find-peak-element/

題意：給一整數 array nums, 找到峰值並返回其 index。nums 中可能有多個峰值, 返回任何一個峰值的 index 即可。

假設 nums[-1] = nums[n] = -∞

設計 O(log(n)) time 的演算法。

Solution：

想法：利用 Binary Search, 從一個位置開始, 不斷地向高處走, 那麼最終一定可以到達一個峰值位置, 根據比較 nums[i − 1], nums[i], nums[i + 1] 三個位置的值來縮小左邊界 or 右邊界, 有以下幾種情況：

  1. nums[i − 1] < nums[i] > nums[i + 1] : i 即為峰值
  2. nums[i − 1] < nums[i] < nums[i + 1] : i 處於上坡, 峰值在右半邊, 故縮小左邊界
  3. nums[i − 1] > nums[i] > nums[i + 1] : i 處於下坡, 峰值在左半邊, 故縮小右邊界
  4. nums[i − 1] > nums[i] < nums[i + 1] : i 處於山谷, 兩側都是上坡, 可以朝任意方向走(這邊我們選擇往右走, 故縮小左邊界)

分析前面四種可能的情況, 我們選擇比較 nums[i]、 nums[i + 1]
➔ 因為這樣可將情況 1、3 是視作一類, 而情況 2、4 視作另一類

cpp
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;

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

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

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