628. 三个数的最大乘积

🟢   🔖  数组 数学 排序  🔗 力扣 LeetCode

题目

Given an integer array nums, find three numbers whose product is maximum and return the maximum product.

Example 1:

Input: nums = [1,2,3]

Output: 6

Example 2:

Input: nums = [1,2,3,4]

Output: 24

Example 3:

Input: nums = [-1,-2,-3]

Output: -6

Constraints:

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

题目大意

给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例 1：

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

输出： 6

示例 2：

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

输出： 24

示例 3：

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

输出： -6

提示：

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

解题思路

我们需要在数组中找到 三个数的最大乘积。为了做到这一点，可以通过以下两种情况来获得最大值：

1. 三个最大的正数 的乘积。
2. 两个最小的负数和一个最大的正数 的乘积。

---

思路一：排序法

• 对数组进行排序，时间复杂度为 O(n log n)。
• 最大乘积可能是最后三个数的乘积（即最大的三个正数）或者前两个数（最小的负数）与最后一个数（最大正数）的乘积。
• 返回这两种情况的较大值。

复杂度分析

• 时间复杂度：O(n log n)，排序需要 O(n log n)。
• 空间复杂度：O(1)，只使用常数空间。

---

思路二：线性扫描法

• 在一次遍历中找到：
  • 最大的三个数（max1, max2, max3）。
  • 最小的两个数（min1, min2）。
• 计算：
  • max1 * max2 * max3（三个最大的正数）。
  • min1 * min2 * max1（两个最小的负数和一个最大的正数）。
• 返回两者的较大值。

复杂度分析

• 时间复杂度：O(n)，仅需一次遍历，在性能上更优，适用于大规模数据。
• 空间复杂度：O(1)，只使用常数空间。

代码

排序法

/**
 * @param {number[]} nums
 * @return {number}
 */
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]
	);
};

线性扫描法

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumProduct = function (nums) {
	// 初始化最大和最小值
	let max1 = -Infinity,
		max2 = -Infinity,
		max3 = -Infinity;
	let min1 = Infinity,
		min2 = Infinity;

	for (let num of 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, min1 * min2 * max1);
};

相关题目

题号	标题	题解	标签	难度	力扣
152	乘积最大子数组	[✓]	数组 动态规划	🟠	🀄️ 🔗