628. 三个数的最大乘积

题目描述

输入一个整数数组 nums，其中可能有负数。

从数组中选出三个不同下标上的数相乘，返回所有选法中乘积的最大值。

示例 1

输入：nums = [1,2,3]
输出：6

解释：1 * 2 * 3 = 6。

示例 2

输入：nums = [1,2,3,4]
输出：24

解释：选 2、3、4，乘积为 24。

示例 3

输入：nums = [-1,-2,-3]
输出：-6

解释：只有三个数，乘积为 -6。

数据范围

3 <= nums.length <= 10^4
-1000 <= nums[i] <= 1000

解题思路：一次遍历维护最值

最大乘积只可能来自两种组合：最大的三个数相乘；或者最小的两个数（两个负数，负负得正）乘最大的数。一次遍历同时维护最小的两个数 min1 ≤ min2 和最大的三个数 max1 ≥ max2 ≥ max3，最后取两种乘积的较大者。

为什么正确

遍历到第 k 个数时，min1、min2 是前 k 个数中最小的两个，max1、max2、max3 是最大的三个。

复杂度分析

时间 O(n)，只遍历一次；空间 O(1)。

易错点

只取最大的三个数会漏掉“两个很小的负数乘最大正数”的情况；更新 max1 时要把旧的 max1、max2 依次下移，不能直接覆盖。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        min1 = min2 = float('inf')
        max1 = max2 = max3 = float('-inf')
        for x in nums:
            if x < min1:
                min1, min2 = x, min1
            elif x < min2:
                min2 = x
            if x > max1:
                max1, max2, max3 = x, max1, max2
            elif x > max2:
                max2, max3 = x, max2
            elif x > max3:
                max3 = x
        return max(max1 * max2 * max3, min1 * min2 * max1)

class Solution {
    public int maximumProduct(int[] nums) {
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        for (int x : nums) {
            if (x < min1) {
                min2 = min1; min1 = x;
            } else if (x < min2) {
                min2 = x;
            }
            if (x > max1) {
                max3 = max2; max2 = max1; max1 = x;
            } else if (x > max2) {
                max3 = max2; max2 = x;
            } else if (x > max3) {
                max3 = x;
            }
        }
        return Math.max(max1 * max2 * max3, min1 * min2 * max1);
    }
}

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int min1 = INT_MAX, min2 = INT_MAX;
        int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
        for (int x : nums) {
            if (x < min1) {
                min2 = min1; min1 = x;
            } else if (x < min2) {
                min2 = x;
            }
            if (x > max1) {
                max3 = max2; max2 = max1; max1 = x;
            } else if (x > max2) {
                max3 = max2; max2 = x;
            } else if (x > max3) {
                max3 = x;
            }
        }
        return max(max1 * max2 * max3, min1 * min2 * max1);
    }
};

func maximumProduct(nums []int) int {
	min1, min2 := math.MaxInt32, math.MaxInt32
	max1, max2, max3 := math.MinInt32, math.MinInt32, math.MinInt32
	for _, x := range nums {
		if x < min1 {
			min1, min2 = x, min1
		} else if x < min2 {
			min2 = x
		}
		if x > max1 {
			max1, max2, max3 = x, max1, max2
		} else if x > max2 {
			max2, max3 = x, max2
		} else if x > max3 {
			max3 = x
		}
	}
	return max(max1*max2*max3, min1*min2*max1)
}

var maximumProduct = function(nums) {
    let min1 = Infinity, min2 = Infinity;
    let max1 = -Infinity, max2 = -Infinity, max3 = -Infinity;
    for (const x of nums) {
        if (x < min1) {
            [min1, min2] = [x, min1];
        } else if (x < min2) {
            min2 = x;
        }
        if (x > max1) {
            [max1, max2, max3] = [x, max1, max2];
        } else if (x > max2) {
            [max2, max3] = [x, max2];
        } else if (x > max3) {
            max3 = x;
        }
    }
    return Math.max(max1 * max2 * max3, min1 * min2 * max1);
};

function maximumProduct(nums: number[]): number {
    let min1 = Infinity, min2 = Infinity;
    let max1 = -Infinity, max2 = -Infinity, max3 = -Infinity;
    for (const x of nums) {
        if (x < min1) {
            [min1, min2] = [x, min1];
        } else if (x < min2) {
            min2 = x;
        }
        if (x > max1) {
            [max1, max2, max3] = [x, max1, max2];
        } else if (x > max2) {
            [max2, max3] = [x, max2];
        } else if (x > max3) {
            max3 = x;
        }
    }
    return Math.max(max1 * max2 * max3, min1 * min2 * max1);
}

载入编辑器，自己跑一遍 →

其他解法

两种解法的候选组合相同：最大三数之积或最小两数与最大数之积；排序法靠排序找到这五个数，一次遍历直接维护它们，省掉排序。

解法 2：排序时间 O(n log n)，空间 O(log n)

先把数组排序。最大乘积只可能来自两种组合：最大的三个数相乘；最小的两个数（可能都是负数）乘以最大的数。取两者较大值。

排序后五个候选数一目了然，代码极短。代价是 O(n log n) 的排序，并且会改动输入顺序。

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])

class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return Math.max(nums[n - 1] * nums[n - 2] * nums[n - 3], nums[0] * nums[1] * nums[n - 1]);
    }
}

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        return max(nums[n - 1] * nums[n - 2] * nums[n - 3], nums[0] * nums[1] * nums[n - 1]);
    }
};

func maximumProduct(nums []int) int {
	sort.Ints(nums)
	n := len(nums)
	return max(nums[n-1]*nums[n-2]*nums[n-3], nums[0]*nums[1]*nums[n-1])
}

var maximumProduct = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    return Math.max(nums[n - 1] * nums[n - 2] * nums[n - 3], nums[0] * nums[1] * nums[n - 1]);
};

function maximumProduct(nums: number[]): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    return Math.max(nums[n - 1] * nums[n - 2] * nums[n - 3], nums[0] * nums[1] * nums[n - 1]);
}

数学专题的其他题目

查看数学全部题目 →