3.4 搜尋最大值

162. Find Peak Element

題目描述

給定一個陣列，定義最大值為比兩邊都大的數字，要求出任意一個最大值的位置。一個陣列中可能存在多個最大值，返回任意一個即可。要求時間複雜度為 $O(\log n)$。

輸入輸出範例

輸入是一個陣列，輸出為最大值的位置。

Input: nums = [1,2,3,1]
Output: 2

最大值 3 出現在位置 2。

題解

為了實現 $O(\log n)$ 的時間複雜度，我們可以對陣列進行二分搜尋。在確保陣列兩端不是最大值後，若當前中點不是最大值，那麼其左右一側必定存在一個最大值。

C++

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

Python

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

複雜度分析

• 時間複雜度: $O(\log n)$，其中 $n$ 是陣列的長度。每次迭代將搜索範圍縮小一半。
• 空間複雜度: $O(1)$，只使用了常數額外空間。