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 多平台发布