线性探测

线性探测

628. 三个数的最大乘积

难度简单378收藏分享切换为英文接收动态反馈

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

示例 1：

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

示例 2：

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

示例 3：

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

1.常规解法

class Solution {public int maximumProduct(int[] nums) {int n=nums.length;//对数组排序Arrays.sort(nums);//考虑前面大于俩个为负数的情况return Math.max(nums[0]*nums[1]*nums[n-1],nums[n-1]*nums[n-2]*nums[n-3]);}
}

2.线性探测解法

思路还是基于上面的思路

class Solution {public int maximumProduct(int[] nums) {//最小的值int min1 =Integer.MAX_VALUE,min2=Integer.MAX_VALUE;//最大的值int max1 =Integer.MIN_VALUE,max2=Integer.MIN_VALUE,max3=Integer.MIN_VALUE;for(int 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 Math.max(min1*min2*max1,max1*max2*max3);}
}