Easy

题目描述

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

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

给你一个整数数组 nums，选择四个不同的下标 w、x、y 和 z，使数对 (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

提示：

  • 如果只需要在数组中找到2个数的最大乘积，你应该选择哪2个数？
  • 我们只需要关心数组中的4个数字。

解题思路

要使乘积差 (a * b) - (c * d) 最大化，我们需要让 a * b 尽可能大，同时让 c * d 尽可能小。

核心思路：

  • 为了使第一个乘积 a * b 最大，我们应该选择数组中最大的两个数
  • 为了使第二个乘积 c * d 最小，我们应该选择数组中最小的两个数

解法分析：

  1. 排序解法：对数组排序，取最大的两个数和最小的两个数
  2. 一次遍历解法（推荐）：通过一次遍历找到最大的两个数和最小的两个数

一次遍历的优势：

  • 时间复杂度更优：O(n) vs O(n log n)
  • 空间复杂度更优：O(1) vs O(1)或O(n)（取决于排序算法）

在遍历过程中，我们维护四个变量：最大值、第二大值、最小值、第二小值。遍历结束后，最大乘积差就是 max1 * max2 - min1 * min2。

代码实现

class Solution {
public:
    int maxProductDifference(vector<int>& nums) {
        int max1 = 0, max2 = 0;  // 最大值和第二大值
        int min1 = INT_MAX, min2 = INT_MAX;  // 最小值和第二小值
        
        for (int num : nums) {
            // 更新最大值和第二大值
            if (num > max1) {
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max2 = num;
            }
            
            // 更新最小值和第二小值
            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
        }
        
        return max1 * max2 - min1 * min2;
    }
};

class Solution:
    def maxProductDifference(self, nums: List[int]) -> int:
        max1 = max2 = 0  # 最大值和第二大值
        min1 = min2 = float('inf')  # 最小值和第二小值
        
        for num in nums:
            # 更新最大值和第二大值
            if num > max1:
                max2 = max1
                max1 = num
            elif num > max2:
                max2 = num
            
            # 更新最小值和第二小值
            if num < min1:
                min2 = min1
                min1 = num
            elif num < min2:
                min2 = num
        
        return max1 * max2 - min1 * min2

public class Solution {
    public int MaxProductDifference(int[] nums) {
        int max1 = 0, max2 = 0;  // 最大值和第二大值
        int min1 = int.MaxValue, min2 = int.MaxValue;  // 最小值和第二小值
        
        foreach (int num in nums) {
            // 更新最大值和第二大值
            if (num > max1) {
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max2 = num;
            }
            
            // 更新最小值和第二小值
            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
        }
        
        return max1 * max2 - min1 * min2;
    }
}

var maxProductDifference = function(nums) {
    let max1 = 0, max2 = 0;  // 最大值和第二大值
    let min1 = Infinity, min2 = Infinity;  // 最小值和第二小值
    
    for (let num of nums) {
        // 更新最大值和第二大值
        if (num > max1) {
            max2 = max1;
            max1 = num;
        } else if (num > max2) {
            max2 = num;
        }
        
        // 更新最小值和第二小值
        if (num < min1) {
            min2 = min1;
            min1 = num;
        } else if (num < min2) {
            min2 = num;
        }
    }
    
    return max1 * max2 - min1 * min2;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
一次遍历（推荐）O(n)O(1)
排序O(n log n)O(1)

说明：

  • 一次遍历解法只需要遍历数组一次，时间复杂度为 O(n)
  • 空间复杂度为 O(1)，只使用了常数个额外变量
  • 排序解法虽然思路简单，但时间复杂度较高，不如一次遍历解法高效