LeetCode 628. 三个数的最大乘积

LeetCode 628 题目原文

628. 三个数的最大乘积
难度：简单
链接：https://leetcode.cn/problems/maximum-product-of-three-numbers/

题目描述

给你一个整型数组nums，在数组中找出由三个数组成的最大乘积，并返回这个最大乘积。

示例

示例1：
输入：nums = [1,2,3]
输出：6

示例2：
输入：nums = [1,2,3,4]
输出：24

示例3：
输入：nums = [-1,-2,-3]
输出：-6

提示

1. 3≤nums.length≤1043 \le nums.length \le 10^43≤nums.length≤104
2. −1000≤nums[i]≤1000-1000 \le nums[i] \le 1000−1000≤nums[i]≤1000

---

费曼学习法讲解破解思路（假装讲给零基础同学）

费曼核心：用大白话讲清楚，找到卡壳的漏洞，简化重讲。

第一步：看懂题目

题目：数组里随便挑3个不同元素相乘，找乘积最大的值。
坑点：负数！
两个负数相乘是正数！
比如数组[-5,-4,1,2,3]：

• 最大三个正数：1×2×3=6
• 最小两个负数 × 最大正数：(-5)*(-4)*3 = 60，明显更大！

👉 所以只有两种候选组合，最大乘积一定出自这二者之一：

1. 排序后，最后面最大的3个数相乘（三个大数）
2. 排序后，最前面最小2个数（很可能是两个负数） × 数组最大的数

我们只算出这两个乘积，返回两者中更大的那个，就全部覆盖所有情况。

为什么不用枚举全部三元组？
数组最多10000个元素，枚举全部组合是O(n3)O(n^3)O(n3)，超级慢，完全不可行。

解法1：排序法（简单好写，面试首选）

思路

1. 将数组从小到大排序
2. 候选1：末尾3个大数nums[-1] * nums[-2] * nums[-3]
3. 候选2：前2个最小数 × 末尾最大数nums[0] * nums[1] * nums[-1]
4. return max(候选1，候选2)
   时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)，排序消耗；空间：原地排序O(1)O(1)O(1)

Python代码，每行详细注释

# 导入类型注解工具，leetcode提交需要ListfromtypingimportList# leetcode固定模板类classSolution:# 定义函数，nums是输入数组，返回int整数defmaximumProduct(self,nums:List[int])->int:# 第一步：数组从小到大排序nums.sort()# 候选方案1：数组排序后，最后三个最大数字相乘product_max_three=nums[-1]*nums[-2]*nums[-3]# 候选方案2：数组前两个最小数字(负数) * 数组最大数字nums[-1]product_two_min_one_max=nums[0]*nums[1]*nums[-1]# 返回两个乘积里面较大的值，就是答案returnmax(product_max_three,product_two_min_one)

测试代码（本地运行）

# 实例化类s=Solution()print(s.maximumProduct([1,2,3]))# 6print(s.maximumProduct([1,2,3,4]))# 24print(s.maximumProduct([-1,-2,-3]))# -6print(s.maximumProduct([-5,-4,1,2,3]))# 60

解法2：一次遍历法（最优时间复杂度O(n)，大数据场景）

费曼讲解：不想排序，只遍历一遍数组，记住5个变量：
最大的3个数 max1>max2>max3；最小2个数 min1<min2
遍历每一个数字，不断更新这5个变量，最后同样算两个候选乘积。

Python代码，每行详细注释

fromtypingimportListclassSolution:defmaximumProduct(self,nums:List[int])->int:# 初始化三个最大值：负无穷，任何数字都比它大max1=max2=max3=float('-inf')# 初始化两个最小值：正无穷，任何数字都比它小min1=min2=float('inf')# 循环遍历数组中每一个数字fornuminnums:# 更新三个最大值，顺序不能乱！先更新最大，再依次向后传递ifnum>max1:# 当前数字比最大的还大，原来的max1变成max2，max2变成max3max3,max2,max1=max2,max1,numelifnum>max2:# 数字介于max1和max2之间，更新max2，旧max2给max3max3,max2=max2,numelifnum>max3:# 数字介于max2和max3之间，只更新第三大max3=num# 更新两个最小值ifnum<min1:# 当前数字比最小的还小，原来最小的变成第二小min2,min1=min1,numelifnum<min2:# 数字介于min1和min2之间，更新第二小min2=num# 候选1：最大三个数相乘candidate1=max1*max2*max3# 候选2：两个最小 × 最大candidate2=min1*min2*max1# 返回较大值returnmax(candidate1,candidate2)

时间复杂度O(n)O(n)O(n)，只遍历数组1次；空间复杂度O(1)O(1)O(1)，只用5个变量，不随数组长度增加。
适合海量数据场景，数组长度极大的时候优先选这个。

费曼查漏：容易踩坑的盲区

1. 全部负数数组：[-5,-4,-3,-2]，排序后[-5,-4,-3,-2]
   候选1：(-4)(-3)(-2) = -24；候选2：(-5)(-4)(-2)=-40，max取-24 ✔
2. 包含0的数组[-3,-2,0,1,2]：(-3)(-2)2 =12 > 012=0
3. 不要暴力三重循环！n=10000，三重循环亿亿次，直接超时。

应用场景举例

1. 金融风控/收益预测
   一组资产的涨跌幅（有正有负），选取3个资产组合，求组合收益乘积最大值。负数代表下跌，两个大跌资产反转（做空）+大涨资产，可以收益最大化。

2. 定价、折扣模型
   商品折扣系数数组，折扣可以是负数（补贴），选3个系数组合，计算总放大系数最大值，用于营销方案测算。

3. 传感器信号处理
   采集一批传感器数据，有正负波动，从中选3个信号相乘，找最强信号组合。

4. 面试算法场景
   这是面试经典数组题，考察对负数乘法的思维，不是单纯排序。

两种方案对比

方案	时间复杂度	优点	缺点	适用场景
排序法	O(n log n)	代码简短，好写，不容易写错	大数据排序稍微慢	普通数组，面试写代码首选
单次扫描	O(n)	最快，只扫一遍	变量更新逻辑容易写反	超大数组、性能敏感场景