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

🟢   🔖  数组 排序 堆（优先队列）  🔗 力扣 LeetCode

题目

Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of(nums[i]-1)*(nums[j]-1).

Example 1:

Input: nums = [3,4,5,2]

Output: 12

Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12.

Example 2:

Input: nums = [1,5,4,5]

Output: 16

Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.

Example 3:

Input: nums = [3,7]

Output: 12

Constraints:

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

题目大意

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

解题思路

问题要求从数组中选择两个不同的下标，使得 (nums[i] - 1) * (nums[j] - 1) 的值最大。最优的选择显然是数组中的两个最大值。

1. 遍历数组，维护两个变量：

   • max：当前最大的数字。
   • second：当前第二大的数字。

2. 遍历时：

   • 如果当前数字比 max 大：
     • 更新 second 为之前的 max。
     • 更新 max 为当前数字。
   • 否则，如果当前数字比 second 大，更新 second。

3. 计算结果为 (max - 1) * (second - 1)。

复杂度分析

• 时间复杂度: O(n)，只需一次遍历数组。
• 空间复杂度: O(1)，仅使用常数级别的额外空间。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function (nums) {
	let max = 0,
		second = 0;
	for (let num of nums) {
		if (num > max) {
			second = max;
			max = num;
		} else if (num > second) {
			second = num;
		}
	}
	return (max - 1) * (second - 1);
};