图解LeetCode——1464. 数组中两元素的最大乘积(难度:简单)

发布于:2023-01-04 ⋅ 阅读:(264) ⋅ 点赞:(0)

一、题目

给你一个整数数组 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^)/ ~ 「干货分享,每天更新」