628. 三个数的最大乘积

628. 三个数的最大乘积

 

 

 

三个数相乘的最大值,有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);
    }

 

上一篇:五一训练包 水题


下一篇:ORACLE19.8.0 DG主库中drop一个pdb,导致备库停止数据同步