跳至主要內容

1913. 两个数对之间的最大乘积差


1913. 两个数对之间的最大乘积差

🟢   🔖  数组 排序  🔗 力扣open in new window LeetCodeopen in new window

题目

The product difference between two pairs (a, b) and (c, d) is defined as (a * b) - (c * d).

  • For example, the product difference between (5, 6) and (2, 7) is (5 * 6) - (2 * 7) = 16.

Given an integer array nums, choose four distinct indices w, x, y, and z such that the product difference between pairs (nums[w], nums[x]) and (nums[y], nums[z]) is maximized.

Return the maximum such product difference.

Example 1:

Input: nums = [5,6,2,7,4]

Output: 34

Explanation: We can choose indices 1 and 3 for the first pair (6, 7) and indices 2 and 4 for the second pair (2, 4).

The product difference is (6 _ 7) - (2 _ 4) = 34.

Example 2:

Input: nums = [4,2,5,9,7,4,8]

Output: 64

Explanation: We can choose indices 3 and 6 for the first pair (9, 8) and indices 1 and 5 for the second pair (2, 4).

The product difference is (9 _ 8) - (2 _ 4) = 64.

Constraints:

  • 4 <= nums.length <= 10^4
  • 1 <= nums[i] <= 10^4

题目大意

两个数对 (a, b)(c, d) 之间的 乘积差 定义为 (a * b) - (c * d)

  • 例如,(5, 6)(2, 7) 之间的乘积差是 (5 * 6) - (2 * 7) = 16

给你一个整数数组 nums ,选出四个 不同的 下标 wxyz ,使数对 (nums[w], nums[x])(nums[y], nums[z]) 之间的 乘积差 取到 最大值

返回以这种方式取得的乘积差中的 最大值

示例 1:

输入: nums = [5,6,2,7,4]

输出: 34

解释: 可以选出下标为 1 和 3 的元素构成第一个数对 (6, 7) 以及下标 2 和 4 构成第二个数对 (2, 4)

乘积差是 (6 _ 7) - (2 _ 4) = 34

示例 2:

输入: nums = [4,2,5,9,7,4,8]

输出: 64

解释: 可以选出下标为 3 和 6 的元素构成第一个数对 (9, 8) 以及下标 1 和 5 构成第二个数对 (2, 4)

乘积差是 (9 _ 8) - (2 _ 4) = 64

提示:

  • 4 <= nums.length <= 10^4
  • 1 <= nums[i] <= 10^4

解题思路

本题要求计算数组中最大乘积差,即用数组中的两个最大值的乘积减去两个最小值的乘积。

  1. 遍历数组
    通过一次遍历,同时找到数组中:

    • 最大值和第二大值maxsecondMax
    • 最小值和第二小值minsecondMin
  2. 更新最大值

    • 如果当前数大于 max,更新 maxsecondMax
    • 否则,如果当前数大于 secondMax,只更新 secondMax
  3. 更新最小值

    • 如果当前数小于 min,更新 minsecondMin
    • 否则,如果当前数小于 secondMin,只更新 secondMin
  4. 计算乘积差

    计算出最大乘积差并返回:max * secondMax - min * secondMin

复杂度分析

  • 时间复杂度O(n),其中 n 是数组长度,只需一次遍历。
  • 空间复杂度O(1),使用了常数变量。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProductDifference = function (nums) {
	let max = 0,
		secondMax = 0,
		min = Infinity,
		secondMin = Infinity;

	for (let num of nums) {
		// 更新最大值
		if (num > max) {
			secondMax = max;
			max = num;
		} else if (num > secondMax) {
			secondMax = num;
		}

		// 更新最小值
		if (num < min) {
			secondMin = min;
			min = num;
		} else if (num < secondMin) {
			secondMin = num;
		}
	}
	// 计算最大乘积差
	return max * secondMax - min * secondMin;
};