每日一题：每天一个新挑战；
循序渐进：从易到难，扎实掌握；
系统分类：按数据结构分类，有助于构建知识框架；
丰富题量：100 道精选题，覆盖简单/中等/困难难度。

给你一个整型数组 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

代码卡片

题目解析

给定一个整数数组 nums，我们需要找到由数组中三个数相乘得到的最大乘积。由于数组中可能存在负数，因此可能需要考虑负数的组合。特别是两个负数的乘积会得到一个正数，这种情况下乘积可能会更大。

方法一：排序法

1、对数组进行排序。

2、最大的乘积可能出现在以下两种情况：

数组中最大的三个正数的乘积。

数组中最小的两个负数与最大的一个正数的乘积。

3、返回上述两种情况中的最大值。

时间复杂度：O(n log n)，排序数组的时间复杂度。
空间复杂度：O(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]
    );
}

方法二：线性扫描

不进行排序，直接通过一次遍历找到数组中最大的三个数和最小的两个数。
计算这两种可能的最大乘积（最大三个数的乘积，最小两个数与最大一个数的乘积）。
返回其中的最大值。

时间复杂度：O(n)，只需要遍历数组一次。
空间复杂度：O(1)，只使用了常量级别的额外空间。

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);
}