LeetCode 解題筆記：628. Maximum Product of Three Numbers

作者：王一哲
日期：2026年7月26日


LeetCode 題目連結：628. Maximum Product of Three Numbers

解題想法

簡單題。題目給一個陣列 $nums$，且 $-1000 \leq nums[i] \leq 1000$，從 $nums$ 之中選取 3 個數字相乘，回傳乘積最大值。先將 $nums$ 由小到大排序，答案可能是選最大的 3 個正整數相乘，或是選 1 個最大的正整數及2 個最小的負整數相乘，回傳兩種選擇的最大值。但是排序的時間複雜度為 $O(n \log n)$，如果想要將時間複雜度降到 $O(n)$ 就不能排序，改用 for 迴圈掃過 $nums$，用 if 更新最大的 3 個數字及最小的 2 個數字，最後再計算乘積最大值。

Python 程式碼

排序。Runtime: 19 ms, beats 64.08%. Memory: 20.50 MB, beats 17.11%.

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        return max(nums[n-1] * nums[n-2] * nums[n-3], nums[0] * nums[1] * nums[-1])

for 迴圈。Runtime: 4 ms, beats 95.92%. Memory: 20.28 MB, beats 78.13%.

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        a = b = c = float('-inf')  # 最大的 3 個數字
        d = e = float('inf')  # 最小的 2 個數字
        for num in nums:
            if num >= a:  # 新的最大值
                a, b, c = num, a, b
            elif num >= b:  # 新的第二大
                b, c = num, b
            elif num > c:  # 新的第三大
                c = num
            if num <= e:  # 新的最小值
                e, d = num, e
            elif num < d:  # 新的第二小
                d = num
        return max(a*b*c, a*d*e)

C++ 程式碼

排序。Runtime: 14 ms, beats 25.29%. Memory: 31.55 MB, beats 46.18%.

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = (int)nums.size();
        return max(nums[n-1] * nums[n-2] * nums[n-3], nums[0] * nums[1] * nums[n-1]);
    }
};

for 迴圈。Runtime: 0 ms, beats 100.00%. Memory: 31.54 MB, beats 46.18%.

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        const int INF = 1000000000;
        int a = -INF, b = -INF, c = -INF;  // 最大的 3 個數字
        int d = INF, e = INF;  // 最小的 2 個數字
        for(int num : nums) {
            if (num >= a) {  // 新的最大值
                c = b; b = a; a = num;
            } else if (num >= b) {  // 新的第二大
                c = b; b = num;
            } else if (num > c) {  // 新的第三大
                c = num;
            }
            if (num <= e) {  // 新的最小值
                d = e; e = num;
            } else if (num < d) {  // 新的第二小
                d = num;
            }
        }
        return max(a*b*c, a*d*e);
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 10.13 MB, beats 61.90%.

int maximumProduct(int* nums, int numsSize) {
    const int INF = 1000000000;
    int a = -INF, b = -INF, c = -INF;  // 最大的 3 個數字
    int d = INF, e = INF;  // 最小的 2 個數字
    for(int i = 0; i < numsSize; i ++) {
        int num = nums[i];
        if (num >= a) {  // 新的最大值
            c = b; b = a; a = num;
        } else if (num >= b) {  // 新的第二大
            c = b; b = num;
        } else if (num > c) {  // 新的第三大
            c = num;
        }
        if (num <= e) {  // 新的最小值
            d = e; e = num;
        } else if (num < d) {  // 新的第二小
            d = num;
        }
    }
    int ans = a*b*c;
    if ((a*d*e) > ans) ans = a*d*e;
    return ans;
}