628. Maximum Product of Three Numbers

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

Input: [1,2,3] Output: 6

IInput: [1,2,3,4] Output: 24

解法1 分情况

这是我最开始想到的笨方法，三个数相乘无非就几种情况：

数组只有3个元素，直接返回3个数乘积；数组不只3个元素，如果全负就是3负乘积，否则可能是3正也可能是2负1正； （2正1负的情况只可能出现在数组只有3个元素时，这里排除掉）注意有0的情况，特别是只有负数和0。

从结果来看，这种做法逻辑写得繁琐，用时和内存其实还行，72ms、25.7MB。

class Solution { public: int maximumProduct(vector<int>& nums) { int len=nums.size(); int ans=0; if(len==3){ ans=nums[2]*nums[1]*nums[0]; //数组只有3个元素，就不用麻烦了 } else{ int Pos=0,Zero=0; int p1=0,p2=0,p3=0; //3个最大正数，p1>p2>p3 int n1=0,n2=0,n3=0; //3个最小负数，n1<n2<n3 for(int x : nums){ if(x>p1){ p3=p2; p2=p1; p1=x; Pos++; } else if(x>p2){ p3=p2; p2=x; Pos++; } else if(x>p3){ p3=x; Pos++; } if(x==0) Zero++; if(x<n1){ n3=n2; n2=n1; n1=x; } else if(x<n2){ n3=n2; n2=x; } else if(x<n3){ n3=x; } } if(Pos==0){ if(Zero==0) ans=n1*n2*n3; //全负，返回3个最小负数乘积 else ans=0; //没有正数，但是有0，返回0 } else{ //其余情况一视同仁，要么是3正要么是1正2负，有0也不影响 ans=max(p1*p2*p3,p1*n1*n2); } } return ans; } };

解法2 遍历

在上面的基础上改进了一下，三个数相乘的最大值，只需要找到数组中最大的三个数和最小的两个数，比较 “最大三个数的乘积” 和 “最小两个数和最大数的乘积”，不需要再讨论是否有负数。

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(int x : nums){ if(x>max1){ max3=max2; max2=max1; max1=x; } else if(x>max2){ max3=max2; max2=x; } else if(x>max3){ max3=x; } if(x<min1){ min2=min1; min1=x; } else if(x<min2){ min2=x; } } return max(max1*max2*max3,min1*min2*max1); } };

解法3 排序

跟上面一个道理，只不过这里先递增排序，然后取最后三位乘积与最后一位和前两位乘积的最大值。

class Solution { public: int maximumProduct(vector<int>& nums) { sort(nums.begin(), nums.end()); int L = nums.size(); return max(nums[L-1]*nums[L-2]*nums[L-3], nums[L-1]*nums[0]*nums[1]); } };

只需用#include 即可使用sort函数，语法描述为：

sort(begin,end)