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:

The length of the given array will be in range [3,10^4] and all elements are in the range [-1000, 1000].
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 (
	"math"
	"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])
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

// 解法二 模拟，时间复杂度 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
}