日期：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)
