目录
一、题目描述
给你一个整型数组 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
二、思路讲解
要找最大乘积，就是找出最大的三个数，或者最大的一个数和最小的两个负数，这就很容易想到排序，排序之后直接取值即可。时间复杂度为O(NlogN)。
那有没有复杂度更低的算法呢？当然有！
其实我们只需遍历一遍数组。定义三个变量a、b、c，分别保存第一大、第二大和第三大的数；定义两个变量z、y，分别保存第一小和第二小的数，遍历的时候更新这些值即可。时间复杂度为O(N)。
三、Java代码实现
class Solution {
public int maximumProduct(int[] nums) {
int a = Integer.MIN_VALUE; //先置为最小值
int b = Integer.MIN_VALUE;
int c = Integer.MIN_VALUE;
int z = Integer.MAX_VALUE; //先置为最大值
int y = Integer.MAX_VALUE;
for(int i : nums){
if(i>a){
c = b;
b = a;
a = i;
}else if(i>b){
c = b;
b = i;
}else if(i>c){
c = i;
}
if(i<z){
y = z;
z = i;
} else if(i<y){
y = i;
}
}
return Math.max((a*b*c), (a*y*z));
}
}
四、时空复杂度分析
时间复杂度： O(N) 遍历一遍数组
空间复杂度： O(1)
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/125047.html
