Given an integer array, find three numbers whose product is maximum and output the maximum product.
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.
原题地址: Maximum Product of Three Numbers
难度: Easy
题意: 找出相乘最大的三个数
思路:
因为数字有正有负,因此相乘最大的三个数分为两种情况:
(1)最大的三个正数
(2)最小的两个负数以及一个最大的正数
代码:
class Solution(object):
def maximumProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
a = b = c = None
d = e = 0x7FFFFFFF
for i in range(len(nums)):
if nums[i] >= a: # 找出最大的三个数
a, b, c = nums[i], a, b
elif nums[i] >= b:
b, c = nums[i], b
elif nums[i] >= c:
c = nums[i] if nums[i] <= e: # 找出最小的两个数
d, e = e, nums[i]
elif nums[i] <= d:
d = nums[i] max_val = 0 # if a > 0 and b > 0 and c > 0:
# max_val = max(max_val, a * b * c) # if a > 0 and d < 0 and e < 0:
# max_val = max(max_val, a * d * e) # if a < 0 and b < 0 and c < 0:
# max_val = a * b * c
max_val = max(a*b*c, a*d*e)
return max_val
时间复杂度: O(n)
空间复杂度: O(1)