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
- code
class Solution:
def maximumProduct(self, nums: List[int]) -> int:
nums.sort()
return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums [-1])
- code
class Solution:
def maximumProduct(self, nums: List[int]) -> int:
smallestTwo = [float('inf')]*2
largestThree = [float('-inf')]*3
for num in nums:
if num <= smallestTwo[0]:
smallestTwo[0] = num
smallestTwo.sort(reverse=True)
if num >= largestThree[0]:
largestThree[0] = num
largestThree.sort()
return max(smallestTwo[0]*smallestTwo[1]*largestThree[2],
largestThree[0]*largestThree[1]*largestThree[2])
- code heapq
class Solution:
def maximumProduct(self, nums: List[int]) -> int:
small2 = [float('-inf')]*2
large3 = [float('-inf')]*3
heapq.heapify(large3)
heapq.heapify(small2)
for i in range(len(nums)):
if nums[i] >= large3[0]:
heapq.heappushpop(large3, nums[i])
if nums[i] <= -small2[0]:
heapq.heappushpop(small2, -nums[i])
return max(large3[0] * large3[1] * large3[2],
heapq.nlargest(1,large3)[0]*small2[0]*small2[1])
- code better heapq
class Solution:
def maximumProduct(self, nums: List[int]) -> int:
mins = heapq.nsmallest(2, nums)
maxs = sorted(heapq.nlargest(3, nums))
product1 = maxs[0] * maxs[1] * maxs[2]
product2 = mins[0] * mins[1] * maxs[2]
return max(product1, product2)