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,104] 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.
这个题目就是需要注意负数的情况即可, 我们如果用排序的话, 比较max(nums[0]*nums[1]*nums[-1], nums[-1]*nums[-2]*nums[-3])即可. T: O(nlgn)
要T: O(n) 的话就需要得到min1, min2, max1, max2, max3同理比较max(min1 * min2 * max1, max1 * max2 * max3)即可.
Code
1) T: O(nlgn)
class Solution:
def maxProduct3nums(self, nums):
nums.sort()
return max(nums[0]*nums[1]*nums[-1], nums[-1]*nums[-2]*nums[-3])
2) T: O(n)
class Solution:
def maxProduct3nums(self, nums):
ans = [1001]*2 + [-1001]*3 # min1, min2, max1, max2, max3
for num in nums:
if num > ans[-1]:
ans[-1], ans[-2], ans[-3] = num, ans[-1], ans[-2]
elif num > ans[-2]:
ans[-2], ans[-3] = num, ans[-2]
elif num > ans[-3]:
ans[-3] = num
if num < ans[0]:
ans[0], ans[1] = num, ans[0]
elif num < ans[1]:
ans[1] = num
return max(ans[0]*ans[1]*ans[-1], ans[-1]*ans[-2]*ans[-3])