LeetCode 628 最大三个数乘积（Maximum Product of Three Numbers）Go 题解：排序与线性扫描两种实现

LeetCode 628 最大三个数乘积Maximum Product of Three NumbersGo 题解排序与线性扫描两种实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文基于 LeetCode-Go 仓库中 leetcode/0628.Maximum-Product-of-Three-Numbers/README.md 的题目与解题思路结合仓库内628. Maximum Product of Three Numbers.go的两种实现与628. Maximum Product of Three Numbers_test.go的完整测试用例深入讲解如何在 O(n log n) 排序与 O(n) 单次扫描两种策略之间做选择并剖析负数、零值等边界场景。读完本文你将掌握这类从数组中挑选 k 个数使乘积/和最大问题的通用分析套路并可直接运行仓库测试验证结论。题目描述给定一个整数数组nums从中找出三个数使其乘积最大并输出该最大乘积。示例 1Input: [1,2,3] Output: 6示例 2Input: [1,2,3,4] Output: 24注意题目约束数组长度范围[3, 10^4]所有元素取值[-1000, 1000]任意三个数的乘积不会超过 32 位有符号整数的表示范围因此不需要考虑大数溢出Go 中直接用int即可。题目大意给定一个整型数组在数组中找出由三个数组成的最大乘积并输出这个乘积。难点在于数组可能同时包含负数与正数直接取最大的三个数并不总是正确答案——例如[-10, -10, 1, 2, 3]最大的三个数是3, 2, 1乘积为 6但真正的最大乘积是(-10) × (-10) × 3 300。核心思路乘积最大值的构成只有两种可能这是本题最关键的分析结论。设数组经处理后我们知道三个最大数降序看是第 1、2、3 大两个最小数升序看是第 1、2 小。乘积最大的三个数只可能是下面两种情况之一三个最大的正数最大值 × 次大值 × 第三大值两个最小的负数 × 一个最大的正数负负得正绝对值最大的两个负数即数值最小的两个数与最大正数相乘能产生一个很大的正数。因此答案就是max( 最小值 × 次小值 × 最大值 , 最大值 × 次大值 × 第三大值 )时间复杂度上仓库 README 明确指出题目的 test case 数据量比较大如果用排序的话时间复杂度高可以直接考虑模拟挑出 3 个数组成乘积最大值必然是一个正数和二个负数或者三个正数。那么选出最大的三个数和最小的二个数对比一下就可以求出最大值了时间复杂度 O(n)。也就是说问题的关键在于只关心最大的三个数与最小的两个数这为 O(n) 解法提供了理论依据。解法一排序法O(n log n)排序法是最直观的实现先整体排序然后直接用上面的公式比较两种候选乘积。仓库中对应实现为 628. Maximum Product of Three Numbers.go 中的maximumProduct// 解法一 排序时间复杂度 O(n log n) func maximumProduct(nums []int) int { if len(nums) 0 { return 0 } res : 1 if len(nums) 3 { for i : 0; i len(nums); i { res res * nums[i] } return res } sort.Ints(nums) if nums[len(nums)-1] 0 { return 0 } return max(nums[0]*nums[1]*nums[len(nums)-1], nums[len(nums)-1]*nums[len(nums)-2]*nums[len(nums)-3]) }实现要点长度防御题目保证数组长度至少为 3但仓库实现额外处理了len(nums) 3的情况——直接把所有元素相乘返回空数组返回 0。这保证了函数在非标准输入下也不会越界。排序后取值nums[0]、nums[1]是最小的两个数最可能是负数nums[len(nums)-1]、nums[len(nums)-2]、nums[len(nums)-3]是最大的三个数。候选一nums[0] * nums[1] * nums[len(nums)-1]对应两个最小负数 × 最大正数候选二nums[len(nums)-1] * nums[len(nums)-2] * nums[len(nums)-3]对应三个最大数两者取max即为答案。复杂度排序开销 O(n log n)空间 O(1)原地排序。解法二线性扫描模拟法O(n)排序虽然简单但本题只关心最大的三个和最小的两个完全可以在一次遍历中用 O(1) 的辅助变量维护这 5 个极值把复杂度降到 O(n)。仓库中的maximumProduct1正是这一思路// 解法二 模拟时间复杂度 O(n) func maximumProduct1(nums []int) int { max : make([]int, 0) max append(max, math.MinInt64, math.MinInt64, math.MinInt64) min : make([]int, 0) min append(min, math.MaxInt64, math.MaxInt64) for _, num : range nums { if num max[0] { max[0], max[1], max[2] num, max[0], max[1] } else if num max[1] { max[1], max[2] num, max[1] } else if num max[2] { max[2] num } if num min[0] { min[0], min[1] num, min[0] } else if num min[1] { min[1] num } } maxProduct1, maxProduct2 : min[0]*min[1]*max[0], max[0]*max[1]*max[2] if maxProduct1 maxProduct2 { return maxProduct1 } return maxProduct2 }实现细节逐行拆解初始化max切片长度为 3初值为math.MinInt64用于容纳最大的三个数min切片长度为 2初值为math.MaxInt64用于容纳最小的两个数。用极值初始化保证第一个元素进来必然命中更新分支。维护最大三个数当前元素大于max[0]时整体后移max[0]←num原max[0]变max[1]原max[1]变max[2]否则依次尝试插入max[1]、max[2]的位置。这是一个插入排序式的滚动窗口复杂度 O(1)。维护最小两个数同理比min[0]小则整体后移否则尝试更新min[1]。最终比较maxProduct1 min[0] * min[1] * max[0]两个最小数负得正× 最大数maxProduct2 max[0] * max[1] * max[2]三个最大数两者取大。复杂度一次遍历 O(n)辅助空间 O(1)。这正是 README 推荐的方案在n接近上限 10^4 时与排序法的差距约 n log n vs n是肉眼可见的。边界情况与正确性讨论把负数、零、重复元素考虑进去是本题拿满分的分水岭。仓库测试文件 628. Maximum Product of Three Numbers_test.go 覆盖了多组典型场景输入期望输出说明[3, -1, 4]-12只有 3 个元素只能全部相乘[1, 2, 3]6全正数取最大三个[1, 2, 3, 4]24全正数2×3×4[2, 3, -2, 4]24一个负数仍是取最大三个正数[-2, 0, -1]0存在 0乘积不可能为正答案为 0[-2, 0, -1, 2, 3, 1, 10]60混合场景(-2)×(-1)×10与2×3×10比较[-10, -10, 1, 2, 3]300经典陷阱两个负数负负得正(-10)×(-10)×3[5, 4, 4, 3]80含重复最大值4×4×5[-4, -3, -2, -1]0解法一全非正数组见下文说明其中两个值得注意的实现细节解法一在全非正数组上的特殊处理maximumProduct在排序后若发现nums[len(nums)-1] 0即最大元素都非正会直接返回 0。这是一个带有约定性质的短路逻辑而maximumProduct1没有这个短路它会算出数学意义上的最大值。测试代码中对maximumProduct1的校验做了相应放宽仅当got ! 0时才要求两者一致注释也明确说明了两者的差异具体见 628. Maximum Product of Three Numbers_test.go 第 106–114 行。防御非标准输入虽然题目保证长度 ≥ 3测试仍包含了[1,2]、[-2]、[0]、[]等退化输入验证两个函数在越界防护上行为正确长度不足时求全部元素的积空数组返回 0。测试用例验证与运行方式仓库采用一题一目录的组织方式测试文件与实现文件放在同一目录实现leetcode/0628.Maximum-Product-of-Three-Numbers/628. Maximum Product of Three Numbers.go测试leetcode/0628.Maximum-Product-of-Three-Numbers/628. Maximum Product of Three Numbers_test.go测试结构使用仓库统一的question628/para628/ans628表格驱动模式每个用例包含输入数组one []int与期望答案one int循环中对两个解法分别断言任何一个用例不通过都会通过t.Fatalf立即失败并打印出入参与实际输出。在仓库根目录执行单题测试go test -v ./leetcode/0628.Maximum-Product-of-Three-Numbers/若想验证仓库声明的100% test coverage项目描述即提到 solutions 具有完整测试覆盖可按根目录 gotest.sh 中的方式对全部题目跑覆盖率go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...仓库根目录的 go.mod 声明了模块github.com/halfrost/LeetCode-GoGo 版本为 1.19并包含structures、template、ctl等本地子模块的replace映射按上述命令即可在 Go 1.19 环境下直接运行。复杂度总结与延伸解法时间复杂度空间复杂度核心思想解法一maximumProduct排序O(n log n)O(1)排序后比较两种候选组合解法二maximumProduct1线性扫描O(n)O(1)单趟维护最大三数与最小两数本题的通用性在于当问题要求在数组中挑选 k 个数使乘积/和最大或最小时先分析答案的构成形态往往能发现只需维护少量极值即可在 O(n) 内求解而不必对全数组排序。类似的思路还可迁移到最大子数组乘积维护最大与最小两个状态、数组中两个数乘积最大等题目中。对照仓库解法二可见用两个长度为 3 与 2 的小切片代替手写多个变量既保持了 O(1) 空间也让更新逻辑清晰可读值得在编码实践中借鉴。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考