[toc]
leetcode 628. 三个数的最大乘积
题目描述
- 三个数的最大乘积
给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
示例 1：
输入：nums = [1,2,3]
输出：6
示例 2：
输入：nums = [1,2,3,4]
输出：24
示例 3：
输入：nums = [-1,-2,-3]
输出：-6
提示：
3 <= nums.length <= 104
-1000 <= nums[i] <= 1000
解题思路
法1
排序+模拟\
- 对数组进行排序
- 找出乘积最大的三个数
- a[0]a[1]a[len-1]
- a[len-1]a[len-2]a[len-3]
这两种情况下可以取到最大值
- 时间复杂度(O(nlogn))
- 空间复杂度(O(1))
执行结果
法1
func maximumProduct(nums []int) int {
l := len(nums)
if l <= 3 {
return nums[1] * nums[2] * nums[0]
}
sort.Ints(nums)
if nums[0] > 0 && nums[l-1] < 0 || nums[0]*nums[1]*nums[l-1] < nums[l-1]*nums[l-2]*nums[l-3] {
return nums[l-1] * nums[l-2] * nums[l-3]
}
return nums[0] * nums[1] * nums[l-1]
}
执行结果：
通过
显示详情
查看示例代码
添加备注
执行用时：
48 ms
, 在所有 Go 提交中击败了
66.67%
的用户
内存消耗：
6.3 MB
, 在所有 Go 提交中击败了
72.73%
的用户
通过测试用例：
92 / 92
炫耀一下:
优化结构
func maximumProduct(nums []int) int {
l := len(nums)
sort.Ints(nums)
if nums[0]*nums[1]*nums[l-1] < nums[l-1]*nums[l-2]*nums[l-3] {
return nums[l-1] * nums[l-2] * nums[l-3]
}
return nums[0] * nums[1] * nums[l-1]
}
执行结果：
通过
显示详情
查看示例代码
添加备注
执行用时：
44 ms
, 在所有 Go 提交中击败了
73.33%
的用户
内存消耗：
6.3 MB
, 在所有 Go 提交中击败了
72.73%
的用户
通过测试用例：
92 / 92
炫耀一下:
本文由mdnice多平台发布
