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提示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(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_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. 三个数的最大乘积

相关推荐

餐饮连锁销量预测：DeepSeek模型与POS系统对接实战指南

中望3d特征报错的原因和简易解决办法（尤其含草图特征）

从Notebook到生产级AI工程：四层架构实战手册

更多资讯

VMware 安装 Windows Server 2003 虚拟机教程与避坑指南

芯片烧录自制还是外包？从量产成本到固件安全的决策指南

Java线程池从入门到实战：核心参数、执行流程与避坑指南

Agentic AI产品化实战：从训练营到可落地的三层设计法

RAG优化别只盯着Embedding：分块、混合检索与重排序才是关键

Uni-app下default未导出报错的排查与修复

今日更新

MATLAB+Yalmip+CPLEX实战：综合能源系统优化调度全流程解析

I3C比I2C快10倍？RK3576实战：速率、DTS配置与混合总线避坑指南

字符串转对象：JSON.parse、new Function与URLSearchParams

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？