Leetcode 628: Maximum Product of Three Numbers

问题描述:

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

给定任意数组,选三个值使其乘积最大

限定条件:
3 <= nums.length <= 10000 (保证至少三个数)
-1000 <= nums[i] <= 1000

思路:
1:如果只有三个数,那么就返回这三个数的乘积,别无其它选择
2:如果有超过三个数,我们才需要制定策略,当然要先排序
(1)如果最大值都小于等于零,最优乘积就是最大三个数乘积
例如(-8,-6,-6,-3,-2,-2,-1,0)
(2)如果最小值都大于等于零,最优乘积就是最大三个数乘积
例如(0,2,3,4,5,8,8,9,9)
(3)其它:即超过三个数且正负数混合,我们通过一定策略可以保证乘积非负。无非以下两种情况求较大值:(最大三个)或(最小两个加最大一个)的较大值。原理如下:我们可以这样想,从排好序的数组左侧(即最小值一侧)选几个数可以使乘积最大?选0个,当然可以,如果最大值的绝对值够大;选1个,不会出现这种情况,因为若这个数为正,则它不够大,若这个数为负,它只贡献了一个负号;选2个,可以,如果这两个数的绝对值够大;选3个,不会出现这种情况,道理同上。

代码如下:

class Solution {
    public int maximumProduct(int[] nums) {
        int last = nums.length - 1;
        
        //case 0: when there are only 3 nums, then there is no choice
        if (last==2) return nums[last]*nums[last-1]*nums[last-2];
        
        //otherwise, we can sort the array to choose the best strategy
        Arrays.sort(nums);
        
        //case 1 and 2: when all nums are nonnegative or when all nums are nonpositive, product = product of largest 3
        if ((nums[last]<=0)||(nums[0]>=0)) return nums[last]*nums[last-1]*nums[last-2];
        
        //case 2: all others case(mix of negative and positive and >3 nums) we can guarantee a nonnegative product
        //there are two possible ways we grab numbers to get the maximum product:
        //(grab the largest 3) or (grab the smallest 2 and the largest 1), no other possibilities
        else{
            return Math.max(nums[last]*nums[last-1]*nums[last-2], nums[0]*nums[1]*nums[last]);
        }
    }
}

时间复杂度:O(nlogn)

上一篇:element 单个日期组件 设置范围


下一篇:Three.js 旋转