1464.md

title	description	keywords
1464. 数组中两元素的最大乘积	LeetCode 1464. 数组中两元素的最大乘积题解，Maximum Product of Two Elements in an Array，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1464. 数组中两元素的最大乘积 数组中两元素的最大乘积 Maximum Product of Two Elements in an Array 解题思路 数组 排序 堆（优先队列）

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

🟢 Easy  🔖  数组 排序 堆（优先队列）  🔗 力扣 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);
};