628. 三个数的最大乘积

一、题目描述

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

• 3 <= nums.length <= 104
• -1000 <= nums[i] <= 1000

二、解题思路

2.1 思路1：排序

先排序，然后再找最大值，可能的情况包括：

1. 都是非负数，或者非正数，此时最大值只能是最后3个值相乘；
2. 正数负数都有，那么最大乘积就只可能是2种情况：3非负、1非负2非正。

2.2 思路2（官方解法）：直接遍历

思路1中实际用到的值包括：3个最大值和2个最小值。

直接遍历数组，拿到这些值，然后最大乘积就只能是2种情况：

1. 3个最大值（3正或3负）;
2. 1个最大值2个最小值（1正2负）。

三、复杂度分析

1）思路1：排序

• 时间 O(nlogn)
• 空间 O(1)

2）思路2（官方解法）：直接遍历

• 时间 O(n)
• 空间 O(1)

四、参考代码

1）思路1：排序

/**
 * 三个数的最大乘积
 * @param nums 数组
 * @return 最大乘积
 */
private int maximumProduct2(int[] nums) {
    int result;
    Arrays.sort(nums);
    if (nums[0] >= 0 || nums[nums.length - 1] <= 0) {
        // 3非负，或3非正
        result = nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3];
    } else {
        // 3非负，或1非负2非正
        int r1 = nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3];
        // 1非负2非正
        int r2 = nums[0] * nums[1] * nums[nums.length - 1];
        result = Math.max(r1, r2);
    }
    return result;
}

2）思路2：直接遍历

/**
 * 三个数的最大乘积
 * @param nums 数组
 * @return 最大乘积
 */
private int maximumProduct(int[] nums) {
    int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
    int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        // 最大值
        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);
}