一、题目描述
给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
示例 1：
输入：nums = [1,2,3]
输出：6
示例 2：
输入：nums = [1,2,3,4]
输出：24
示例 3：
输入：nums = [-1,-2,-3]
输出：-6
提示：
3 <= nums.length <= 104
-1000 <= nums[i] <= 1000
二、思路讲解
要找最大乘积，就是找出最大的三个数，或者最大的一个数和最小的两个负数，这就很容易想到排序，排序之后直接取值即可。时间复杂度为O(NlogN)。
那有没有复杂度更低的算法呢？当然有！
其实我们只需遍历一遍数组。定义三个变量a、b、c，分别保存第一大、第二大和第三大的数；定义两个变量z、y，分别保存第一小和第二小的数，遍历的时候更新这些值即可。时间复杂度为O(N)。
三、Java代码实现
class Solution { public int maximumProduct(int[] nums) { int a = Integer.MIN_VALUE; //先置为最小值 int b = Integer.MIN_VALUE; int c = Integer.MIN_VALUE; int z = Integer.MAX_VALUE; //先置为最大值 int y = Integer.MAX_VALUE; for(int i : nums){ if(i>a){ c = b; b = a; a = i; }else if(i>b){ c = b; b = i; }else if(i>c){ c = i; } if(i<z){ y = z; z = i; } else if(i<y){ y = i; } } return Math.max((a*b*c), (a*y*z)); } }
四、时空复杂度分析
时间复杂度： O(N) 遍历一遍数组
空间复杂度： O(1)
