Array 628 三个数的最大乘积

2020-10-19

思路：

如果数组长度是 3 ，直接返回连成；

按照冒泡排序的方法，将最大的三位数换到最后 3 位的位置上。

初审题，没有考虑的问题是，数组可能存在负数，因此将数组分为 4 种情况

数组长度为 3 ，直接计算
数组全为正数，全为负数，只有一个负数，排序之后的最大 3 个数乘积
数组有超过或者有 2 个元素为负数，比较最小的两个负数与最大正数的乘积和最大3 个正数的乘积。
但是因此用了排序

public int maximumProduct(int[] nums) {
        int len = nums.length;
        if (len == 3) return nums[0]*nums[1]*nums[2];
        // 找出证数和负数的边界
        // int[] nums = new int [len];
        Arrays.sort(nums);
        int edge = -1;
        for(int i = 0;i < len ;i++) {
            if(nums[i] < 0) edge = i;
            else break;
        }

        // int i = edge ,j =edge + 1;
        int multy =  nums[len-1]*nums[len-2]*nums[len-3];
        if((edge <= 0) || (edge == len -1)){
            // 都是正数 或者 全为负数或只有一个负数
            return multy ;
        }else {
            // 存在两个以上负数，比较最大的两个负数和最大正数的乘积 和 3 个最大正数的乘积
            int multy1 = nums[0]*nums[1]*nums[len-1];
            return multy > multy1 ? multy : multy1;

        }
    }

复杂度分析

时间复杂度：O(NlogN)，其中 N是数组的长度,主要是排序。
空间复杂度：O(log N)，为排序使用的空间

方法二：线性扫描

在方法一中，我们实际上只要求出数组中最大的三个数以及最小的两个数，因此我们可以不用排序，用线性扫描直接得出这五个数。

定义两个极大值 min1 和 min2 ，三个极小值 max1，max2，max3。
依次遍历每个数 num
- 如果 num < min1，就让 min1（极小值） = num，min2 （次小值） = min1。
- 如果 min1 < num < min2 ，那么 num 就是此小值，赋值 min2
- 如果 min1 < min2 < num ,num就不是我们要找的最小的两个数，就不管了
- 如果 num > max1(第一次类似无穷小)，num 就是最大值，num1 = num，一次递推，一直让 num1 保持最大值，num2 保持次大值，num3 保持次次大值。
这样结束之后就会找到最大的 3 个数和最小的 2 个数。

这种方法就像漏斗一样，筛选出最大的 3 个数和最小的 2 个数。要筛选出两个最小值，就需要设置两个边界，算法精妙之处就在于：

min 最开始设置为 int 的最大值，这样任何一个值都不会比它大，然后将第一个数值付给 min ，依次比较找到最小值。
边界值互换数值的时候，求最大值要从大到小赋值，避免数据被污染。一直要保持 min 是最小值，max 是最大值。


// 方法二 ：线性扫描
int min1 = Integer.MAX_VALUE,min2 = Integer.MAX_VALUE,
max1 = Integer.MIN_VALUE,max2 = Integer.MIN_VALUE,max3 = Integer.MIN_VALUE;

// 遍历数组
for(int num : nums){
    // 找打最小值和次小值
    if(num <= min1){
        // 判断最大值
        min2 = min1;
        min1 = num;
    }else if(num <= min2){
        // 判断次大值
        min2 = num;
    }

    // 找到最大的是三个数
    if(num >= max1){
        // 判断最大值 
        // max2 = max1;
        // max3 = max2;
        // max1 = num;
        // 从小到大一次赋值
        max3 = max2;
        max2 = max1;
        max1 = num;
    }else if (num >= max2){
        // 判断次大值
        max3 = max2;
        max2 = num;
    }else if( num >= max3){
        max3 = num;
    }
}

return Math.max(min1*min2*max1, max1*max2*max3);