[LeetCode]Ar628. 三个数的最大乘积

🚩传送门：https://leetcode-cn.com/problems/maximum-product-of-three-numbers/

题目

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

示例 1：

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

示例 2：

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

示例 3：

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

解题思路：排序

首先将数组排序。

1. 如果数组中全是非负数（num≥0），则排序后最大的三个数相乘即为最大乘积；
2. 如果数组中全是非正数（num≤0），则排序后最大的三个数相乘即为最大乘积。
3. 如果数组中有正有负
   • 最大乘积可能是三个最大正数的乘积
   • 最大乘积可能是两个最小负数（即绝对值最大）与最大正数的乘积。

综上，我们在给数组排序后，分别求出三个最大正数的乘积，以及两个最小负数与最大正数的乘积，二者之间的最大值即为所求答案。

复杂度分析

时间复杂度：，其中 是数组 的长度 。

空间复杂度： 或 ，由排序的空间开销决定。

官方代码

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

解题思路：线性扫描

实际上只要求出数组中最大的三个数以及最小的两个数，因此可以不用排序，线性扫描出这五个数。

复杂度分析

时间复杂度：，其中 是数组 的长度 。

空间复杂度： 。

官方代码

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) {
            //1.如果比最小的小就是最小的
            if (x < min1) {
                min2 = min1;
                min1 = x;
            }
            //2.如果不小于最小的但是比第二小的小就是第二小
            else if (x < min2) {
                min2 = x;
            }
            //3.如果比最大的大就是最大的
            if (x > max1) {
                max3 = max2;
                max2 = max1;
                max1 = x;
            }
            //4.如果不大于最大的但是比第二大的大就是第二大
            else if (x > max2) {
                max3 = max2;
                max2 = x;
            }
            //5.如果不大于最大、第二大的但是比第三大的大就是第三大
            else if (x > max3) {
                max3 = x;
            }
        }
        //6.比较返回结果
        return Math.max(min1 * min2 * max1, max1 * max2 * max3);
    }
}