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 炫耀一下: