有序三元组中的最大值 II

标签: 数组

难度: Medium

给你一个下标从 0 开始的整数数组 nums 。

请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。

下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

示例 1：

输入：nums = [12,6,1,2,7]
输出：77
解释：下标三元组 (0, 2, 4) 的值是 (nums[0] - nums[2]) * nums[4] = 77 。
可以证明不存在值大于 77 的有序下标三元组。

示例 2：

输入：nums = [1,10,3,4,19]
输出：133
解释：下标三元组 (1, 2, 4) 的值是 (nums[1] - nums[2]) * nums[4] = 133 。
可以证明不存在值大于 133 的有序下标三元组。

示例 3：

输入：nums = [1,2,3]
输出：0
解释：唯一的下标三元组 (0, 1, 2) 的值是一个负数，(nums[0] - nums[1]) * nums[2] = -3 。因此，答案是 0 。

提示：

  • 3 <= nums.length <= 105
  • 1 <= nums[i] <= 106

Submission

运行时间: 100 ms

内存: 28.3 MB

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        ans = preMax = maxD = 0
        for x in nums:
            if (v := maxD * x) > ans: ans = v
            if (v := preMax - x) > maxD: maxD = v
            if x > preMax: preMax = x
        return ans

Explain

这个题解使用了一次遍历的方法。我们首先定义一个变量 preMax 来存储遍历过的元素中的最大值，定义一个变量 maxD 来存储遍历过的元素中 preMax 和当前元素差的最大值。在遍历过程中，我们首先计算当前元素与 maxD 的乘积，如果这个乘积大于之前的答案，则更新答案。然后，我们计算 preMax 与当前元素的差，如果这个差大于 maxD，则更新 maxD。最后，如果当前元素大于 preMax，则更新 preMax。这样，在遍历结束时，我们就能得到最大的三元组值。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        ans = preMax = maxD = 0  # 初始化答案、前面元素的最大值和最大差值
        for x in nums:  # 遍历数组
            if (v := maxD * x) > ans: ans = v  # 如果当前元素和最大差值的乘积大于答案，则更新答案
            if (v := preMax - x) > maxD: maxD = v  # 如果前面元素的最大值和当前元素的差大于最大差值，则更新最大差值
            if x > preMax: preMax = x  # 如果当前元素大于前面元素的最大值，则更新最大值
        return ans  # 返回答案

Explore

题解中使用的一次遍历方法不是直接遍历所有可能的三元组(i, j, k)，而是通过维护历史最大值和历史最大差值来间接计算可能的最大三元组值。这种方法依赖于特定的数学逻辑和假设，即我们可以通过当前元素与历史最大差值的乘积来检测最大的三元组值。然而，这种方法可能无法确保覆盖所有可能的三元组组合，因为它没有显式考虑三元组的所有其他组合可能性，而是依赖于当前的遍历状态和历史记录。

在题解中，`preMax` 变量通过遍历并更新来始终保存遍历到的元素中的最大值。因此，这个变量在任何时刻都代表了到目前为止遇到的最大值，即在遍历到当前元素时，它代表的是之前所有元素的最大值。这就确保了`preMax`所代表的是最大值 i 而非 k，因为 k 是在之后的元素中被考虑的。

要验证题解方法的正确性，最佳方式是通过一系列的测试用例，包括各种边界条件和特殊情况。可以构造不同的数组，尤其是那些元素顺序和大小差异明显的，来检查算法是否能够正确地更新和维护`preMax`和`maxD`，并最终得出正确的最大三元组值。同时，还可以通过理论分析来检查是否有漏洞或逻辑上的错误。如果存在某些情况下无法得到正确答案的可能，需要调整或更新算法逻辑以处理这些特殊情况。

在题解中，`maxD` 是在遍历过程中，每次遇到一个新元素 x 时，计算`preMax`（即之前所有元素的最大值）与当前元素 x 的差，并检查这个差是否是最大的。因为`preMax`是在当前元素 x 之前的所有元素中的最大值，所以计算得到的差值自然满足 i < j 的条件，其中 i 是`preMax`对应的元素位置，j 是当前元素 x 的位置。这样，通过逻辑确保了每次更新`maxD`时，都是基于满足 i < j 条件的最大差值。