leecode 628. 三个数的最大乘积

题目描述

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

示例 1：

输入：nums = [1,2,3]

输出：6

示例 2：

输入：nums = [1,2,3,4]

输出：24

示例 3：

输入：nums = [-1,-2,-3]

输出：-6

3 <= nums.length <= 104

-1000 <= nums[i] <= 1000

链接：https://leetcode-cn.com/problems/maximum-product-of-three-numbers

要求时间复杂度为O(n)，空间复杂度为O(1)

只需要找到最大的三个数字，对于序列中只有正数而言的序列，就需要找序列中绝对值最大的数，对于序列中含有负数的序列，就需要找两个最小的负数以及一个最大的正数，总结下来就是找最大的三个数以及最小的两个数，此时用到的空间为常数，因此为O(1),时间复杂度为O(n)，因为需要循环遍历一遍整个数组。初始化时，max1，max2,max3初始化为INT_MIN，min1，min2初始化为INT_MAX。这些数字寻找的过程是对于最小的数而言，想用该数字与最小的数字比，如果最小的数字小于当前min1，那么需要更新min1和min2；对于寻找最大的数字而言，就要用该数字与max1先作比较，如果该数字比max1大的话，就需要更新max1。最后取两个最小数字与最大数字的乘积以及三个最大数字乘积这两个数值的最大值。

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int max1=INT_MIN,max2=INT_MIN,max3=INT_MIN;
        int min1=INT_MAX,min2=INT_MAX;
        for(auto x:nums)
        {
            if(x < min1)
            {
                min2 = min1;
                min1 = x;
            }
            else if(x < min2)
            {
                min2 = x;
            }

            if(x > max1)
            {
                max3 = max2;
                max2 = max1;
                max1 = x;
            }
            else if( x > max2)
            {
                max3 = max2;
                max2 = x;
            }
            else if(x > max3)
            {
                max3 = x;

            }
        }
        return max(min1*min2*max1 , max1*max2*max3);
    }
};

           

如果没有时间复杂度的限制，那么常规的做法是sort，排序之后直接找三个最大正数的乘积，以及两个最小负数与最大正数的乘积，取二者之间的最大值即可。

牛客网上的样例没有限制数组中数字的取值范围，需要在结果输出时做数据类型的转化，将int转化为 long long。