题目详情

给你一个整型数组nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例 1：

输入：输入：nums = [1,2,3,4]
输出：24
重点考察：线性扫描

注意到的点：以开始作者的想法是排序之后找到三个最大的值，但是实际情况会出现数组中有正有负的情况，所以当选出的三个数字有两个负数和一个正数时也会产生最大的乘积
eg：输入：nums = [1,2,3,-4,-8,10]
如果只是排序后选出三个最大值，那么应该是2 * 3 * 10 = 60
但是实际应该为-4 * -8 * 10 = 320

Java代码

    class Solution {
        public int maximumProduct(int[] nums) {
            Arrays.sort(nums);
            int n = nums.length;
            return Math.max(nums[0] * nums[1] * nums[n -1],nums[n-1]*nums[n-2]*nums[n-3]);

        }
    }

时间复杂度为n*logn，比较两种情况下哪种得到的结果会更大一些

Java代码（线性扫描）

  class Solution {
        public int maximumProduct(int[] nums) {
            //定义两个最小值，默认为int值最大
            int min1 = Integer.MAX_VALUE;
            int min2 = Integer.MAX_VALUE;
            //定义三个最大值，默认为int值最小
            int max1 = Integer.MIN_VALUE;
            int max2 = Integer.MIN_VALUE;
            int max3 = Integer.MIN_VALUE;

            for(int x:nums){
                 //找出两个最小的值
                if(x < min1){
                    //当有一个数字比min1还要小，那么就说明三个数字中x最小，min1第二小，min2第三小
                    min2 = min1;
                    //当遍历到x发现x小于min1，那么x就是最小的；
                    min1 = x;
                }else if(x<min2){
                    //假如出现遇到的x比min1大，但是比min2小，这时候要更新min2
                    min2 = x;
                }

                //找出三个最大的值
                if(x > max1){
                    //同理，当遍历到一个数字比max1还要大，那就说明四个数中，x最大，max1第二大，max2第三大，max3第四大
                    max3 = max2;
                    max2 = max1;
                    max1 = x;
                }else if(x > max2){
                    max3 = max2;
                    max2 = x;
                } else if(x > max3){
                    max3 = x;
                }
            }
            return Math.max(max1*min1*min2,max1*max2*max3);

        }
  }

因为不需要排序，所以时间复杂度为n

总结

这个算法的核心在于，找到五个值，分别为数组中三个最大值，两个最小值，比较两个最小值和一个最大值相乘和三个最大值相乘哪个更大一些。
同时这道题可以扩散到所有找出数组中n个最大值或者n个最小值的题型。排序时间复杂度高，可以考虑使用线性扫描