一、题目
给你一个整数数组 nums
,请你选择数组的两个不同下标 i
和 j
,使 (nums[i]-1)*(nums[j]-1)
取得最大值。
请你计算并返回该式的 最大值。
二、示例
2.1> 示例 1:
【输入】nums = [3,4,5,2]
【输出】12
【解释】如果选择下标 i=1 和 j=2(下标从 0 开始),则可以获得最大值,(nums[1]-1)(nums[2]-1) = (4-1)(5-1) = 3*4 = 12 。
2.2> 示例 2:
【输入】nums = [1,5,4,5]
【输出】16
【解释】选择下标 i=1 和 j=3(下标从 0 开始),则可以获得最大值 (5-1)*(5-1) = 16 。
2.3> 示例 3:
【输入】nums = [3,7]
【输出】12
提示:
2
<= nums.length <=500
1
<= nums[i] <=10^3
三、解题思路
3.1> 思路1:排序 + 计算最大两个值
由于题目中描述的是,要求出(nums[i]-1)*(nums[j]-1)
取得最大值,那么其实我们只要能够保证nums[i]和nums[j]的值是整个数组中排名前两位的就可以了。
那么首先,我们就会想到先调用Arrays.sort(...)
方法对nums数组
进行排序,由于排序后的结果是升序遍历,所以我们获取数组中最后两个元素:nums[nums.length - 1]
和nums[nums.length - 2]
进行计算即可。具体实现请参照:4.1> 代码1:排序 + 计算最大两个值
3.2> 思路2:一次遍历 + 计算最大两个值
在思路1中,由于我们对数组首先进行了排序操作,所以,会造成一定的性能损耗,执行用时并不理想。那么,我们其实也可以不对数组nums进行排队,而是创建两个变量a和b,分别用来记录当前最大的两个值。如果我们遍历到的元素小于a和b的话,那么直接循环下一次即可。否则,我们会根据a和b的对比,来将新的元素替换到a和b之间更小的那个值。这样,我们通过一次遍历,就可以获得数组中最大的两个值了。然后再对a和b进行计算就可以了。具体实现请参照:4.2> 代码1:一次遍历 + 计算最大两个值
四、代码实现
4.1> 代码1:排序 + 计算最大两个值
class Solution {
public int maxProduct(int[] nums) {
Arrays.sort(nums);
return (nums[nums.length - 1] - 1) * (nums[nums.length - 2] - 1);
}
}
4.2> 代码2:一次遍历 + 计算最大两个值
本解法因为不需要排序操作的性能消耗,所以,执行时间更好。
class Solution {
public int maxProduct(int[] nums) {
int a = nums[0], b = nums[1];
for (int i = 2; i < nums.length; i++) {
if (nums[i] <= a && nums[i] <= b) continue;
if (a <= b) a = nums[i];
else b = nums[i];
}
return (a - 1) * (b - 1);
}
}
今天的文章内容就这些了:
写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」