0628. Maximum Product of Three Numbers

# 628. Maximum Product of Three Numbers#

## 题目 #

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

``````Input: [1,2,3]
Output: 6
``````

Example 2:

``````Input: [1,2,3,4]
Output: 24
``````

Note:

1. The length of the given array will be in range [3,10^4] and all elements are in the range [-1000, 1000].
2. Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.

## 解题思路 #

• 给出一个数组，要求求出这个数组中任意挑 3 个数能组成的乘积最大的值。
• 题目的 test case 数据量比较大，如果用排序的话，时间复杂度高，可以直接考虑模拟，挑出 3 个数组成乘积最大值，必然是一个正数和二个负数，或者三个正数。那么选出最大的三个数和最小的二个数，对比一下就可以求出最大值了。时间复杂度 O(n)

## 代码 #

``````
package leetcode

import (
"sort"
)

// 解法一 排序，时间复杂度 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])
}

// 解法二 模拟，时间复杂度 O(n)
func maximumProduct1(nums []int) int {
n1, n2, n3 := -1<<63, -1<<63, -1<<63
n4, n5 := 0, 0
for _, v := range nums {
if v > n1 {
n3 = n2
n2 = n1
n1 = v
} else if v > n2 {
n3 = n2
n2 = v
} else if v > n3 {
n3 = v
}
if v < n4 {
n5 = n4
n4 = v
} else if v < n5 {
n5 = v
}
}
if n2*n3 > n4*n5 {
return n1 * n2 * n3
}
return n1 * n4 * n5
}

``````

Sep 6, 2020