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提示3≤nums.length≤1043 \le nums.length \le 10^43≤nums.length≤104−1000≤nums[i]≤1000-1000 \le nums[i] \le 1000−1000≤nums[i]≤1000费曼学习法讲解破解思路假装讲给零基础同学费曼核心用大白话讲清楚找到卡壳的漏洞简化重讲。第一步看懂题目题目数组里随便挑3个不同元素相乘找乘积最大的值。坑点负数两个负数相乘是正数比如数组[-5,-4,1,2,3]最大三个正数1×2×36最小两个负数 × 最大正数(-5)*(-4)*3 60明显更大 所以只有两种候选组合最大乘积一定出自这二者之一排序后最后面最大的3个数相乘三个大数排序后最前面最小2个数很可能是两个负数 × 数组最大的数我们只算出这两个乘积返回两者中更大的那个就全部覆盖所有情况。为什么不用枚举全部三元组数组最多10000个元素枚举全部组合是O(n3)O(n^3)O(n3)超级慢完全不可行。解法1排序法简单好写面试首选思路将数组从小到大排序候选1末尾3个大数nums[-1] * nums[-2] * nums[-3]候选2前2个最小数 × 末尾最大数nums[0] * nums[1] * nums[-1]return max(候选1候选2)时间复杂度O(nlogn)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_threenums[-1]*nums[-2]*nums[-3]# 候选方案2数组前两个最小数字(负数) * 数组最大数字nums[-1]product_two_min_one_maxnums[0]*nums[1]*nums[-1]# 返回两个乘积里面较大的值就是答案returnmax(product_max_three,product_two_min_one)测试代码本地运行# 实例化类sSolution()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个数 max1max2max3最小2个数 min1min2遍历每一个数字不断更新这5个变量最后同样算两个候选乘积。Python代码每行详细注释fromtypingimportListclassSolution:defmaximumProduct(self,nums:List[int])-int:# 初始化三个最大值负无穷任何数字都比它大max1max2max3float(-inf)# 初始化两个最小值正无穷任何数字都比它小min1min2float(inf)# 循环遍历数组中每一个数字fornuminnums:# 更新三个最大值顺序不能乱先更新最大再依次向后传递ifnummax1:# 当前数字比最大的还大原来的max1变成max2max2变成max3max3,max2,max1max2,max1,numelifnummax2:# 数字介于max1和max2之间更新max2旧max2给max3max3,max2max2,numelifnummax3:# 数字介于max2和max3之间只更新第三大max3num# 更新两个最小值ifnummin1:# 当前数字比最小的还小原来最小的变成第二小min2,min1min1,numelifnummin2:# 数字介于min1和min2之间更新第二小min2num# 候选1最大三个数相乘candidate1max1*max2*max3# 候选2两个最小 × 最大candidate2min1*min2*max1# 返回较大值returnmax(candidate1,candidate2)时间复杂度O(n)O(n)O(n)只遍历数组1次空间复杂度O(1)O(1)O(1)只用5个变量不随数组长度增加。适合海量数据场景数组长度极大的时候优先选这个。费曼查漏容易踩坑的盲区全部负数数组[-5,-4,-3,-2]排序后[-5,-4,-3,-2]候选1(-4)(-3)(-2) -24候选2(-5)(-4)(-2)-40max取-24 ✔包含0的数组[-3,-2,0,1,2](-3)(-2)2 12 0120不要暴力三重循环n10000三重循环亿亿次直接超时。应用场景举例金融风控/收益预测一组资产的涨跌幅有正有负选取3个资产组合求组合收益乘积最大值。负数代表下跌两个大跌资产反转做空大涨资产可以收益最大化。定价、折扣模型商品折扣系数数组折扣可以是负数补贴选3个系数组合计算总放大系数最大值用于营销方案测算。传感器信号处理采集一批传感器数据有正负波动从中选3个信号相乘找最强信号组合。面试算法场景这是面试经典数组题考察对负数乘法的思维不是单纯排序。两种方案对比方案时间复杂度优点缺点适用场景排序法O(n log n)代码简短好写不容易写错大数据排序稍微慢普通数组面试写代码首选单次扫描O(n)最快只扫一遍变量更新逻辑容易写反超大数组、性能敏感场景
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提示3≤nums.length≤1043 \le nums.length \le 10^43≤nums.length≤104−1000≤nums[i]≤1000-1000 \le nums[i] \le 1000−1000≤nums[i]≤1000费曼学习法讲解破解思路假装讲给零基础同学费曼核心用大白话讲清楚找到卡壳的漏洞简化重讲。第一步看懂题目题目数组里随便挑3个不同元素相乘找乘积最大的值。坑点负数两个负数相乘是正数比如数组[-5,-4,1,2,3]最大三个正数1×2×36最小两个负数 × 最大正数(-5)*(-4)*3 60明显更大 所以只有两种候选组合最大乘积一定出自这二者之一排序后最后面最大的3个数相乘三个大数排序后最前面最小2个数很可能是两个负数 × 数组最大的数我们只算出这两个乘积返回两者中更大的那个就全部覆盖所有情况。为什么不用枚举全部三元组数组最多10000个元素枚举全部组合是O(n3)O(n^3)O(n3)超级慢完全不可行。解法1排序法简单好写面试首选思路将数组从小到大排序候选1末尾3个大数nums[-1] * nums[-2] * nums[-3]候选2前2个最小数 × 末尾最大数nums[0] * nums[1] * nums[-1]return max(候选1候选2)时间复杂度O(nlogn)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_threenums[-1]*nums[-2]*nums[-3]# 候选方案2数组前两个最小数字(负数) * 数组最大数字nums[-1]product_two_min_one_maxnums[0]*nums[1]*nums[-1]# 返回两个乘积里面较大的值就是答案returnmax(product_max_three,product_two_min_one)测试代码本地运行# 实例化类sSolution()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个数 max1max2max3最小2个数 min1min2遍历每一个数字不断更新这5个变量最后同样算两个候选乘积。Python代码每行详细注释fromtypingimportListclassSolution:defmaximumProduct(self,nums:List[int])-int:# 初始化三个最大值负无穷任何数字都比它大max1max2max3float(-inf)# 初始化两个最小值正无穷任何数字都比它小min1min2float(inf)# 循环遍历数组中每一个数字fornuminnums:# 更新三个最大值顺序不能乱先更新最大再依次向后传递ifnummax1:# 当前数字比最大的还大原来的max1变成max2max2变成max3max3,max2,max1max2,max1,numelifnummax2:# 数字介于max1和max2之间更新max2旧max2给max3max3,max2max2,numelifnummax3:# 数字介于max2和max3之间只更新第三大max3num# 更新两个最小值ifnummin1:# 当前数字比最小的还小原来最小的变成第二小min2,min1min1,numelifnummin2:# 数字介于min1和min2之间更新第二小min2num# 候选1最大三个数相乘candidate1max1*max2*max3# 候选2两个最小 × 最大candidate2min1*min2*max1# 返回较大值returnmax(candidate1,candidate2)时间复杂度O(n)O(n)O(n)只遍历数组1次空间复杂度O(1)O(1)O(1)只用5个变量不随数组长度增加。适合海量数据场景数组长度极大的时候优先选这个。费曼查漏容易踩坑的盲区全部负数数组[-5,-4,-3,-2]排序后[-5,-4,-3,-2]候选1(-4)(-3)(-2) -24候选2(-5)(-4)(-2)-40max取-24 ✔包含0的数组[-3,-2,0,1,2](-3)(-2)2 12 0120不要暴力三重循环n10000三重循环亿亿次直接超时。应用场景举例金融风控/收益预测一组资产的涨跌幅有正有负选取3个资产组合求组合收益乘积最大值。负数代表下跌两个大跌资产反转做空大涨资产可以收益最大化。定价、折扣模型商品折扣系数数组折扣可以是负数补贴选3个系数组合计算总放大系数最大值用于营销方案测算。传感器信号处理采集一批传感器数据有正负波动从中选3个信号相乘找最强信号组合。面试算法场景这是面试经典数组题考察对负数乘法的思维不是单纯排序。两种方案对比方案时间复杂度优点缺点适用场景排序法O(n log n)代码简短好写不容易写错大数据排序稍微慢普通数组面试写代码首选单次扫描O(n)最快只扫一遍变量更新逻辑容易写反超大数组、性能敏感场景
