三个数相乘的最大值,有2种可能,(1)3个最大的正数(2)2个最小的负数和1个最大的正数。
方法一:先排序,排序后最小的负数和最大的正数位置就是确定的了
(1)必然是nums[n-3],nums[n-2],nums[n-1]
(2)必然是nums[0],nums[1],nums[n-1]
时间O(nlogn),空间O(logn)
1 public int maximumProduct(int[] nums) { 2 Arrays.sort(nums); 3 int n=nums.length; 4 return Math.max(nums[0]*nums[1]*nums[n-1],nums[n-3]*nums[n-2]*nums[n-1]); 5 }
方法二:本题实际上就是要找出最大的3个数和最小的2个数,加起来一个是5个值,
要找出这5个值除了排序后通过下标确定,还有种方法就是遍历的时候找出来,类比遍历数组找出最小值
时间O(n),空间O(1)
public int maximumProduct(int[] nums) { int min1=Integer.MAX_VALUE,min2=min1; int max1=Integer.MIN_VALUE,max2=max1,max3=max1; for(int num:nums){ if(num<min1){ min2=min1; min1=num; }else if(num<min2){ min2=num; } if(num>max1){ 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); }