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:

1. The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
2. 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);
    }
};