题解 | #三个数的最大乘积#

算法思想一：排序

解题思路：

首先将数组排序
1、如果数组中全是非负数，则排序后最大的三个数相乘即为最大乘积；如果全是非正数，则最大的三个数相乘同样也为最大乘积。
2、如果数组中有正数有负数，则最大乘积既可能是三个最大正数的乘积，也可能是两个最小负数（即绝对值最大）与最大正数的乘积。
3、综上，在给数组排序后，分别求出三个最大正数的乘积，以及两个最小负数与最大正数的乘积，二者之间的最大值即为所求答案。
图解：

代码展示：

Python版本

class Solution:
    def solve(self , A ):
        # write code here
        # 数组排序
        A.sort()
        # 最大三个数的乘积
        onenums = A[-3] * A[-2] * A[-1]
        # 最小两个数乘积 与 最大数之间的乘积
        twonums = A[0] * A[1] * A[-1]
        # 返回两个数的最大值
        return max(onenums, twonums)

复杂度分析

时间复杂度 $O(NlogN)$ ：Python内置排序算法时间复杂度 $O(NlogN)$

空间复杂度 $O(N)$ ：Python内置排序算法空间复杂度 $O(N)$ ，两个变量空间O(1)

算法思想二：线性遍历

解题思路：

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

1、定义max1、max2、max3为第一、第二、第三大的数，min1、min2为第一、第二小的数

2、遍历更新上述五个变量

3、最后返回 $max1*max2*max3$ 和 $max1*min1*min2$ 中最大值

注：最后需要强制转换为long类型

代码展示：

JAVA版本

import java.util.*;
public class Solution {
    /**
     * 最大乘积
     * @param A int整型一维数组 
     * @return long长整型
     */
    public long solve (int[] A) {
        // write code here
        // 最小的和第二小的
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        // 最大的、第二大的和第三大的
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        // 顺序遍历查找最小的两个数、最大的三个数
        for(int i = 0;i < A.length;i ++){
            if(A[i] < min1){//更新最小值
                min2 = min1;
                min1 = A[i];
            }else if(A[i] < min2){//更新第二小
                min2 = A[i];
            }
            if (A[i] > max1){//更新最大值
                max3 = max2;
                max2 = max1;
                max1 = A[i];
            }else if(A[i] > max2){//更新第二大
                max3 = max2;
                max2 = A[i];
            }else if(A[i] > max3){//更新第三大
                max3 = A[i];
            }
        }
        return Math.max((long)min1 * min2 * max1,(long) max1 * max2 * max3);
    }
}

复杂度分析

时间复杂度 $O(N)$ ：N为数组的长度，只需要遍历一次数组时间为 $O(N)$

空间复杂度 $O(1)$ ：仅使用5个变量常数级空间