LeetCode 2874. 有序三元组中的最大值 II - 题解与优化

LeetCode 2874. 有序三元组中的最大值 II - 题解与优化
🧩 题目描述
给你一个下标从 0 开始的整数数组 nums，请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。

一个下标三元组 (i, j, k) 的值定义为：

css
复制
编辑
(nums[i] - nums[j]) * nums[k]
如果所有合法的三元组值都是负数，则返回 0。

📌 示例
示例 1：
makefile
复制
编辑
输入: nums = [12,6,1,2,7]
输出: 77
解释: (0,2,4) => (12 - 1) * 7 = 77
示例 2：
makefile
复制
编辑
输入: nums = [1,10,3,4,19]
输出: 133
解释: (1,2,4) => (10 - 3) * 19 = 133
示例 3：
makefile
复制
编辑
输入: nums = [1,2,3]
输出: 0
解释: 唯一三元组为 (0,1,2) => (1 - 2) * 3 = -3 < 0
🧠 解题思路
我们需要计算所有 (i, j, k) 满足 i < j < k 的 (nums[i] - nums[j]) * nums[k]，要求找出最大值。若暴力三重循环，时间复杂度为 $O(n^3)$，在数据范围最大为 $10^5$ 时显然无法接受。

我们需要进行 优化。

✅ 思路优化
观察表达式：

css
复制
编辑
(nums[i] - nums[j]) * nums[k]
我们可以重写为：

复制
编辑
(diff) * nums[k]，其中 diff = nums[i] - nums[j]
我们只需要在每个 k 前，提前预处理好最大的 diff 值即可。

💡 线性扫描法（单次遍历）
我们可以维护：

pre: 遍历到当前下标时，左边所有元素的最大值（用于模拟 nums[i]）

diff: 遍历到当前位置时，最大的 (nums[i] - nums[j])，只要有 i < j

最终答案为：所有 (diff * nums[k]) 的最大值

✅ 状态转移
python
复制
编辑
diff = max(diff, pre - nums[i])
ans = max(ans, diff * nums[i])
pre = max(pre, nums[i])
💻 代码实现（Python）
python
复制
编辑
class Solution:
def maximumTripletValue(self, nums: List[int]) -> int:
ans = diff = 0
pre = nums[0] # 初始化 pre 为 nums[0]
for i in range(1, len(nums)):
ans = max(ans, diff * nums[i])
diff = max(diff, pre - nums[i])
pre = max(pre, nums[i])
return ans
⏱️ 时间复杂度分析
时间复杂度：O(n)，只遍历了一次数组。

空间复杂度：O(1)，只用了常数空间保存中间变量。

🧪 测试用例
输入 输出 说明
[12,6,1,2,7] 77 (0,2,4) 最大
[1,10,3,4,19] 133 (1,2,4) 最大
[1,2,3] 0 唯一组合结果为负数
📌 总结
本题的关键在于将三重循环转化为一次线性遍历，利用前缀最大值和差值预处理技巧，实现高效的解法。是一道非常典型的优化练习题，适合考察对表达式结构的理解和状态维护能力。