LeetCode 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,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.
解法一
思路
想要找到积最大的三个数,那就是要找到最大的三个数,比如[1, 2, 3, 4]
中积最大的三个数就是[2, 3, 4]
。但这样对么?注意到题目里说到数组元素的值可能是负数,这样情况就不一样了,比如[-4, -5, 1, 2, 3, 4]
,这时积最大的三个数就是[-4, -5, 4]
(积为80),而非[2, 3, 4]
(积为24)。
当考虑到负数后,我们就能发现,积最大的三个数的特征一定是:[正数最大的数, 正数第二大的数, 正数第三大的数]
或者[正数最大的数, 负数最大的数, 负数第二大的数]
。更一般地,其特征一定是:[最大的数, 第二大的数, 第三大的数]
或者[最大的数, 最小的数, 第二小的数]
。
Python
class Solution(object):
def maximumProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max_1 = -sys.maxsize
max_2 = -sys.maxsize
max_3 = -sys.maxsize
min_1 = sys.maxsize
min_2 = sys.maxsize
for num in nums:
if num > max_1:
max_3 = max_2
max_2 = max_1
max_1 = num
elif num > max_2:
max_3 = max_2
max_2 = num
elif num > max_3:
max_3 = num
if num < min_1:
min_2 = min_1
min_1 = num
elif num < min_2:
min_2 = num
return max(max_1 * max_2 * max_3, max_1 * min_1 * min_2)
Java
public class Solution {
public int maximumProduct(int[] nums) {
int max1 = Integer.MIN_VALUE;
int max2 = Integer.MIN_VALUE;
int max3 = Integer.MIN_VALUE;
int min1 = Integer.MAX_VALUE;
int min2 = Integer.MAX_VALUE;
for (int num : nums) {
if (num > max1) {
max3 = max2;
max2 = max1;
max1 = num;
} else if (num > max2) {
max3 = max2;
max2 = num;
} else if (num > max3) {
max3 = num;
}
if (num < min1) {
min2 = min1;
min1 = num;
} else if (num < min2) {
min2 = num;
}
}
return Math.max(max1 * max2 * max3, max1 * min1 * min2);
}
}
C++
class Solution {
public:
int maximumProduct(vector<int> &nums) {
int max1 = INT_MIN;
int max2 = INT_MIN;
int max3 = INT_MIN;
int min1 = INT_MAX;
int min2 = INT_MAX;
for (int num : nums) {
if (num > max1) {
max3 = max2;
max2 = max1;
max1 = num;
} else if (num > max2) {
max3 = max2;
max2 = num;
} else if (num > max3) {
max3 = num;
}
if (num < min1) {
min2 = min1;
min1 = num;
} else if (num < min2) {
min2 = num;
}
}
return max(max1 * max2 * max3, max1 * min1 * min2);
}
};