1464. 数组中两元素的最大乘积

题目描述：

给你一个整数数组 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

---

解题分析及思路：

本题可以采用排序或直接遍历即可

方法一：排序

将原数组排序后，取最大的两个值即可。

func maxProduct(nums []int) int {
	sort.Ints(nums)
	return (nums[len(nums)-1] - 1) * (nums[len(nums)-2] - 1)
}

复杂度：

• 时间复杂度：O(n*logn)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:4 ms,击败了62.03% 的Go用户
• 内存消耗:2.8 MB,击败了79.75% 的Go用户

方法二：遍历

遍历找出两个最大的数即可。

func maxProduct(nums []int) int {
	var index1 = 0
	var max1 = math.MinInt
	for index := 0; index < len(nums); index++ {
		if nums[index] > max1 {
			index1 = index
			max1 = nums[index]
		}
	}
	var max2 = math.MinInt
	for index := 0; index < len(nums); index++ {
		if nums[index] > max2 && index != index1 {
			max2 = nums[index]
		}
	}
	return (max1 - 1) * (max2 - 1)
}

复杂度：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:4 ms,击败了62.03% 的Go用户
• 内存消耗:2.8 MB,击败了100.00% 的Go用户