LEETCODE 1464. Maximum Product of Two Elements in an Array 解题思路分析

题目大意:

数组中两元素的最大乘积

给你一个整数数组 nums,请你选择数组的两个不同下标 i 和 j,使 (nums[i]-1)*(nums[j]-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:

输入:nums = [1,5,4,5]
输出:16
解释:选择下标 i=1 和 j=3(下标从 0 开始),则可以获得最大值 (5-1)*(5-1) = 16 。

示例 3:

输入:nums = [3,7]
输出:12

提示:

  • 2 <= nums.length <= 500
  • 1 <= nums[i] <= 10^3

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1464

解题思路分析:

由于题目中没有负数,因此最大乘积一定来自数组中最大的两个数字。我们可以遍历一遍数组,取得数组中的最大值与次大值,然后用这两个数字分别减一之后相乘即是返回结果。

另外更简单的办法是将数组排序,然后取出最大的前两个数字,再分别减去一之后相乘即可。

实现代码:

public int maxProduct(int[] nums) {
    int max1=0,max2=0;
    for(int n : nums){
        if(n>=max1){
            max2=max1;
            max1=n;
        }else if(n>=max2){
            max2=n;
        }
    }
    return (max1-1)*(max2-1);
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Maximum Product of Two Elements in an Array.

Memory Usage: 39.3 MB, less than 100.00% of Java online submissions for Maximum Product of Two Elements in an Array.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1464-maximum-product-of-two-elements-in-an-array-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。