题目详情

Given an integer array, find three numbers whose product is maximum and output the maximum product.

输入一个大小大于等于三的数组，给出其中任意三个数乘积中的最大乘积

Example 1:

Input: [1,2,3]

Output: 6

Example 2:

Input: [1,2,3,4]

Output: 24

想法

• 这道题最主要的是要考虑正负数的情况。
• 如果全都是正数相乘比较大，就取三个最大值相乘即可。
• 如果负数的绝对值比较大，我们可以取绝对值最大的两个负数参与相乘，最后比较一下两种算法的乘积哪个大。

解法一 时间复杂度O(n)

• 这个解法写起来麻烦一点，判断条件比较多，但是时间复杂度为O(n)

public int maximumProduct(int[] nums) {        Integer max1 = Integer.MIN_VALUE;Integer max2 = max1;Integer max3 = max1;        Integer min1 = Integer.MAX_VALUE;Integer min2 = min1;                for(int num : nums){            if(num > max1){                max3 = max2;                max2 = max1;                max1 = num;            }else if(num > max2){                max3 = max2;                max2 = num;            }else if(num > max3){                max3 = num;            }                        if(num < min1){                min2 = min1;                min1 = num;            }else if(num < min2){                min2 = num;            }                    }                        return Math.max(max1*max2*max3, max1*min1*min2);    }

解法二 预排序

• 先对数组进行预排序的算法比较简洁，但是时间复杂度为O(nlogn)

public int maximumProduct(int[] nums) {                 Arrays.sort(nums);         int a = nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3];         int b = nums[0] * nums[1] * nums[nums.length - 1];         return a > b ? a : b;    }