LeetCode 尋找峰值元素：二分查找與線性掃描解法詳解

問題描述

峰值元素是指其值嚴格大於左右相鄰元素的元素。給定一個輸入數組 nums，其中任意相鄰元素不相等（nums[i] ≠ nums[i+1]），請找出任意一個峰值元素並返回其索引。數組可能包含多個峰值，返回任意一個即可。可假設 nums[-1] = nums[n] = -∞。

例如：輸入 [1,2,3,1]，輸出索引 2（元素 3 為峰值）。

解題思路

方法一：線性掃描（O(n)）

最直觀的方法是遍歷數組，檢查每個元素是否大於其左右鄰居。處理邊界情況：首尾元素只需與唯一鄰居比較。時間複雜度 O(n)，空間複雜度 O(1)。

方法二：二分查找（O(log n)）

雖然數組無序，但峰值的存在性保證了二分查找的可行性。核心觀察：若 mid < mid+1，則右側必存在峰值；反之左側必存在峰值。這是因為數組兩端趨向 -∞，單調上升段的終點必為峰值。

class Solution {
public:
    int findPeakElement(vector& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1])
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
};

代碼實現（線性掃描版）

class Solution {
public:
    int findPeakElement(const vector& num) {
        int len = num.size();
        if (len <= 1) return 0;
        if (num[0] > num[1]) return 0;
        if (num[len-1] > num[len-2]) return len-1;
        for (int i = 1; i < len-1; ++i)
            if (num[i] > num[i-1] && num[i] > num[i+1])
                return i;
        return 0;
    }
};

複雜度分析

• 線性掃描：時間 O(n)，空間 O(1)
• 二分查找：時間 O(log n)，空間 O(1)

二分查找雖然理論更優，但對於小規模數據線性掃描常數因子更小，實際性能可能更好。