162. Find Peak Element

📘 題目敘述

peak element 是指一個元素，它嚴格大於它左右相鄰的元素。

給你一個 0-indexed 整數陣列 nums，請找出任意一個 peak element，並回傳它的 index。

如果陣列中有多個 peak，回傳其中任意一個的 index 都可以。

你可以想像：

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

也就是說，陣列邊界外的元素都視為負無限大，所以邊界元素也有可能成為 peak。

你必須寫出時間複雜度為 O(log n) 的演算法。

條件限制

1 <= nums.length <= 1000
-2^31 <= nums[i] <= 2^31 - 1
對所有合法的 i，都有 nums[i] != nums[i + 1]

🧠 解題思路

這題的關鍵不是去檢查每個位置是不是 peak，而是利用二分搜的方式判斷：

peak 一定存在某一邊，我可以根據中間點和右邊那格的大小關係，決定往哪一側縮。

我這份程式的核心判斷是：

如果 nums[m] > nums[m + 1]
- 代表在 m 這個位置往右是往下降
- 那 peak 一定存在在左半邊，包含 m
- 所以我可以把右界縮成 r = m
如果 nums[m] < nums[m + 1]
- 代表在 m 這個位置往右是往上升
- 那 peak 一定存在在右半邊
- 所以我把左界改成 l = m + 1

這個想法成立的原因是：

如果現在是上坡，那一直往右走，最後不是遇到某個下降點形成 peak，就是一路走到最右邊，而最右邊也會是 peak
如果現在是下坡，那 peak 一定在左邊，因為你不可能一路下降到左邊界都沒有比兩側大的點

所以整個過程中，我不是在找「唯一的 peak」，而是在維護：

目前 [l, r] 這段範圍內一定至少有一個 peak

每次用 m 和 m + 1 的大小關係把不可能的那一邊丟掉，最後當 l == r 時，這個位置就是某個 peak。

另外你前面也特別處理了：

n == 1
n == 2

雖然其實這份二分寫法不特判也能做，但照你的程式碼，我就照你的流程解釋。

也就是說，這題的核心就是：

用二分搜判斷目前中間位置是往上坡還是下坡，藉此縮小範圍，最後停下來的位置就是 peak。

所有變數

n：陣列長度
l：二分搜尋目前範圍的左界
r：二分搜尋目前範圍的右界
m：目前區間的中間位置

🪜 主要流程步驟

1. 先處理長度很小的特例

int n = nums.size();
if (n == 1) {
    return 0;
} else if (n == 2) {
    if (nums[0] > nums[1]) {
        return 0;
    }
    return 1;
}

這裡你先把 n == 1 和 n == 2 分開處理。

如果只有一個元素，那它左右外面都可以想成 -∞，所以它自己一定是 peak，直接回傳 0。

如果有兩個元素：

比較大的那個一定是 peak
所以直接回傳較大值的 index 即可

這樣做完之後，後面的二分搜尋就只會處理 n >= 3 的情況。

2. 設定二分搜尋範圍

int l = 0, r = n - 1;

這裡表示：

我目前要在整個陣列範圍內找某個 peak
一開始搜尋範圍就是整段 [0, n - 1]

後面每次都會根據 m 和 m + 1 的大小關係，把範圍縮小。

3. 只要區間還沒縮成一點，就繼續二分

while (l < r) {
    int m = (l + r) / 2;

這裡每次都先取中間位置 m。

因為你的判斷會用到 nums[m + 1]，所以這份寫法用的是：

當 l < r 時才進迴圈

這樣可以保證：

m < r
所以 m + 1 一定合法

4. 如果 `nums[m] > nums[m + 1]`，代表右邊在下降，peak 在左半邊或就是 m

if (nums[m + 1] < nums[m]) {
    r = m;
}

這一步是整題最核心的判斷之一。

如果：

nums[m] > nums[m + 1]

表示從 m 走到 m + 1 是下坡。

那這代表什麼？

代表 peak 不可能只存在於 m + 1 右邊那一側。
因為現在在 m 已經比右邊高了，所以：

m 自己有可能就是 peak
或者左邊某處會有 peak

因此這時我可以放心把範圍縮成：

[l, m]

也就是 r = m。

注意這裡不是 r = m - 1，因為 m 本身也可能是答案，不能丟掉。

5. 如果 `nums[m] < nums[m + 1]`，代表右邊在上升，peak 一定在右半邊

else {
    l = m + 1;
}

如果：

nums[m] < nums[m + 1]

表示現在往右是上坡。

那這時 peak 一定存在於右半邊。

原因是：

如果這個上坡之後某處開始下降，那個轉折點就是 peak
如果一路上升到最右端，那最右邊也會是 peak，因為右邊界外是 -∞

所以左半邊不需要再保留，直接把：

l = m + 1

代表接下來只在右邊找。

6. 為什麼最後 `l == r` 時，這格一定是 peak

整個二分過程中，你一直維護一件事：

目前區間 [l, r] 內一定至少有一個 peak

每次根據上坡或下坡，把不可能的那一側丟掉，但都保留「一定有 peak」的那一側。

最後當：

l == r

代表區間只剩下一個位置。

既然這個區間內還是保證有 peak，那剩下這一格就一定是某個 peak。

所以最後直接回傳 l 就可以。

7. 最後回傳答案

return l;

當 while (l < r) 結束時，l 和 r 會相等，這個位置就是找到的 peak index。

⏱️ 複雜度

設 n = nums.length。

時間複雜度：O(log n)
- 每次二分都把搜尋範圍縮小一半。
空間複雜度：O(1)
- 只用了固定數量的變數。

💻 程式碼實作

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) {
            return 0;
        } else if (n == 2) {
            if (nums[0] > nums[1]) {
                return 0;
            }
            return 1;
        }
        int l = 0, r = n - 1;
        while (l < r) {
            int m = (l + r) / 2;
            if (nums[m + 1] < nums[m]) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
};

🔗 題目連結

https://leetcode.com/problems/find-peak-element/