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

难度: 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⁴
1 <= nums[i] <= 10⁴

Submission

运行时间: 125 ms

内存: 17.3 MB

class Solution:
    def maxProductDifference(self, nums: List[int]) -> int:
        fMax = max(nums)
        nums.remove(fMax)
        sMax = max(nums)
        nums.remove(sMax)
        fMin = min(nums)
        nums.remove(fMin)
        sMin = min(nums)
        nums.remove(sMin)
        return (fMax * sMax) - (fMin * sMin)

Explain

该题目要求找出四个不同的下标，使得由这四个下标对应的数构成的两个数对的乘积差最大。为了实现这一目标，题解的思路是：首先找出数组中的最大的两个数，这两个数相乘会得到可能的最大乘积；接着找出数组中的最小的两个数，这两个数相乘会得到可能的最小乘积。最后，用最大的乘积减去最小的乘积，得到的结果即为所求的最大乘积差。操作过程中，每次找到一个最大或最小的数后，都将其从数组中移除，以确保不会重复使用同一元素。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def maxProductDifference(self, nums: List[int]) -> int:
        # 找到并移除最大的数
        fMax = max(nums)
        nums.remove(fMax)
        # 找到并移除次大的数
        sMax = max(nums)
        nums.remove(sMax)
        # 找到并移除最小的数
        fMin = min(nums)
        nums.remove(fMin)
        # 找到并移除次小的数
        sMin = min(nums)
        nums.remove(sMin)
        # 计算最大乘积差
        return (fMax * sMax) - (fMin * sMin)

Explore

在处理包含重复元素的数组时，仅通过值来移除元素可能会导致意外地移除具有相同值但不同下标的元素。为避免这种情况，可以在找到最大或最小的数时记录下它们的下标，而不是直接移除这些值。这样，即使值相同，也能确保使用的是不同的实例。另外，可以使用更先进的数据结构，如优先队列（最大堆和最小堆），来管理这些值及其下标，确保选择的是不同的元素。

直接修改数组（如通过移除元素）可能会影响算法的准确性，特别是在并发环境或后续需要使用完整数组的场景中。一个更好的方法是不修改原数组，而是使用数据结构来跟踪最大和最小值的下标。例如，可以先复制数组并在复制上进行排序，然后从排序后的数组中直接读取最大和最小的值。这样可以避免修改原始数组，同时简化逻辑。

如果数组长度小于四，那么不可能找到四个不同的下标来形成两对数，因此这种情况下算法不适用。在实际应用中，应该首先检查数组的长度。如果数组长度小于四，应直接返回错误或特定的值（如0或异常），表明无法进行所需的操作。

存在使用排序的方法，可以简化实现并避免修改原数组。具体方法是：首先对数组进行一次完整的排序，排序后，数组的前两个元素将是最小的两个数，数组的最后两个元素将是最大的两个数。通过这种方法，可以直接读取这些值来计算最大乘积差。这种方法的时间复杂度为O(n log n)，通常比多次遍历寻找最大最小值更高效，特别是在大数据集上。