当前位置：首页 > article >正文

解决问题：2874. 有序三元组中的最大值 II

article 2025/1/31 2:55:34

解决问题：2874. 有序三元组中的最大值 II

问题描述

给定一个整数数组 nums，我们需要从所有满足 (i < j < k) 的下标三元组 ((i, j, k)) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0。每个下标三元组的值定义为：

[
\text{value} = (nums[i] - nums[j]) \times nums[k]
]

输入示例：

nums = [12,6,1,2,7] → 输出：77
nums = [1,10,3,4,19] → 输出：133
nums = [1,2,3] → 输出：0

思路

要解决这个问题，我们的目标是从所有符合条件的三元组中找到最大值。给出的计算方式是 ( (nums[i] - nums[j]) \times nums[k] )，其中 (i < j < k)。
我们需要对三元组的选择方式进行优化，避免使用暴力解法（(O(n^3)) 时间复杂度），从而能够处理较大的输入规模。

暴力解法

最初的暴力解法会通过三重循环来遍历所有可能的三元组，计算其对应的值，最后返回最大的结果。

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n, res = len(nums), 0
        for i in range(n):
            for j in range(i+1, n):
                for k in range(j+1, n):
                    res = max(res, (nums[i] - nums[j]) * nums[k])
        return res

时间复杂度分析：
此解法的时间复杂度为 (O(n^3))，因为我们使用了三重循环来遍历所有可能的三元组。对于 (n \leq 10^5) 的情况，显然会超时。

优化方案

我们可以优化代码，避免暴力法的低效。我们只需要用到一遍遍历和两个辅助变量来记录当前所需的最大值和最小值，从而优化到 (O(n)) 的时间复杂度。

1. 关键观察

我们可以简化问题：

对于每个 j（作为中间元素），我们需要计算：
[
(nums[i] - nums[j]) \times nums[k]
]
其中 i 是比 j 小的索引，k 是比 j 大的索引。为了使结果最大化，我们希望：
- ( nums[i] ) 尽量大，选择 i 前面的最大值。
- ( nums[k] ) 尽量大，选择 k 后面的最大值。

2. 实现

我们可以通过以下方法优化：

使用 pre 记录 nums 中当前遍历元素之前的最大值。
使用 diff 记录当前元素之前的差值 nums[i] - nums[j]。
使用 ans 记录当前最大的三元组值。

具体实现代码如下：

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        ans = diff = pre = 0
        for x in nums:
            ans = max(ans, diff * x)  # 当前差值与后续的 x 计算
            diff = max(diff, pre - x)  # 更新差值
            pre = max(pre, x)  # 更新前缀最大值
        return ans

代码解释

变量初始化:
- ans：记录当前的最大三元组值。
- diff：记录当前 i < j 时 nums[i] - nums[j] 的最大值。
- pre：记录当前 i < j 时，nums[i] 的最大值。
遍历 nums:
- 对于每个元素 x：
  - 使用 diff * x 来更新 ans，它代表了当前 nums[i] - nums[j] 乘以后续的 nums[k] 的值。
  - 更新 diff，即计算 nums[i] - nums[j] 的最大差值。
  - 更新 pre，即计算当前索引前的最大元素。
返回结果：
- 遍历结束后，ans 就是最大的三元组值。

时间复杂度

这段代码只遍历了一遍数组，因此时间复杂度是 (O(n))，非常高效。
空间复杂度是 (O(1))，因为我们只使用了常数级别的额外空间。

测试用例

示例 1：
```
nums = [12, 6, 1, 2, 7]
# 输出：77
```
解释：下标三元组 (0, 2, 4) 的值是 ( (12 - 1) \times 7 = 77 )。
示例 2：
```
nums = [1, 10, 3, 4, 19]
# 输出：133
```
解释：下标三元组 (1, 2, 4) 的值是 ( (10 - 3) \times 19 = 133 )。
示例 3：
```
nums = [1, 2, 3]
# 输出：0
```
解释：唯一的下标三元组 (0, 1, 2) 的值是负数，(1 - 2) \times 3 = -3，因此返回 0。