LeetCode 628 Maximum Product of Three Numbers

LeetCode

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

Example 1:

Input: nums = [1,2,3]
Output: 6

Example 2:

Input: nums = [1,2,3,4]
Output: 24

Example 3:

Input: nums = [-1,-2,-3]
Output: -6

Constraints:

3 <= nums.length <= 10<sup>4</sup> -1000 <= nums[i] <= 1000

题目大意：

求数组任意三个数的最大乘积

排序法解题思路：

数学题，正负数分开，最大只可以是排序后最大的三个数(全正，全负)或最大整数乘以最小两个负数(正负均有)

解题步骤：

N/A

注意事项：

1. Python代码：

   def maximumProduct(self, nums: List[int]) -> int:
   	nums.sort()
   	return max(nums[-1] * nums[-2] * nums[-3], nums[-1] * nums[0] * nums[1])

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(1)

---

Heap算法II解题思路：

由上述思路进一步优化，不需要全部排序，只需要知道最大的3个数和最小的两个数即可

Python代码：

def maximumProduct2(self, nums: List[int]) -> int:
	largest = heapq.nlargest(3, nums)
	smallest = heapq.nsmallest(2, nums)
	return max(largest[0] * largest[1] * largest[2], largest[0] * smallest[0] * smallest[1])

算法分析：

时间复杂度为O(n)，空间复杂度O(1)