LeetCode 162. Find Peak Element 詳解

題目：峰值元素定義為嚴格大於左右鄰居的元素。給定數組 nums，相鄰元素不相等 (nums[i] != nums[i+1])，找到任一峰值下標。想像 nums[-1] = nums[n] = -∞。要求 O(log n) 時間複雜度。

範例：nums = [1,2,3,1] → 峰值 3，下標 2。

核心洞察：二分查找的正確性

對於中間位置 mid：

• 若 nums[mid] < nums[mid+1]，說明右側必存在峰值（因為右邊界是 -∞，上升趨勢最終必須轉折）。
• 若 nums[mid] > nums[mid+1]，說明左側（含 mid）必存在峰值。

因此每次比較 mid 與 mid+1，即可將搜索範圍減半。這是「爬坡」思想：總往高處走，最終必到達峰頂。

標準二分模板 (C++ / Python / Java)

// C++
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < nums[mid + 1])
                l = mid + 1;
            else
                r = mid;
        }
        return l; // l == r 即為峰值位置
    }
};

# Python
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        while l < r:
            mid = (l + r) // 2
            if nums[mid] < nums[mid + 1]:
                l = mid + 1
            else:
                r = mid
        return l

// Java
class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < nums[mid + 1])
                l = mid + 1;
            else
                r = mid;
        }
        return l;
    }
}

為什麼這能行？數學證明

定義 f(i) = nums[i]，虛擬邊界 f(-1)=f(n)=-∞。考慮任意區間 [L, R]，若 f(mid) < f(mid+1)，則 f 在 [mid+1, R] 上「最終」必有峰值（因為右邊界是 -∞，連續上升不可能永遠持續）。同理另一側。這保證了二分方向的正確性。

關鍵細節

• 循環條件 l < r：當 l == r 時區間縮減為單點，即為答案。
• 不需檢查 mid-1：只比較 mid 與 mid+1 即可決定方向，簡化邏輯。
• 相鄰不相等：題目保證 nums[i] != nums[i+1]，避免了平台期判斷困難。
• 返回任一峰值：可能有多個峰值，算法找到的是二分路徑上的某一個。

複雜度分析

面試延伸與變體

1. Peak Index in a Mountain Array (LeetCode 852)：數組先嚴格遞增後嚴格遞減，同樣二分找頂點。
2. Find Peak Element II (LeetCode 1901)：二維矩陣找峰值，可對行/列二分，或用「爬坡」O(m+n) 解法。
3. 允許相鄰相等：需處理平台期，向任一方向延伸至不相等處再判斷，最壞 O(n)。
4. 二分查找的通用模式：單調性判斷 + 邊界收斂，適用於「在隱含單調性中查找邊界」的問題。

總結

Find Peak Element 是二分查找「非典型應用」的經典教案。它打破了「二分只能用於有序數組」的誤區，展示了利用邊界條件與局部單調性進行決策的強大思想。面試中能清晰講出「為什麼往高處走必有峰值」，並寫出無邊界錯誤的二分模板，是演算法功力的重要標誌。