跳至主要內容

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


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

🟢   🔖  数组 排序 堆(优先队列)  🔗 力扣open in new window LeetCodeopen in new window

题目

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,请你选择数组的两个不同下标 ij,使 (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);
};