DEV Community
·
2874. 有序三元组 II 的最大值
💡
原文英文，约700词，阅读约需3分钟。
📝
内容提要
给定一个整数数组，求所有满足 i < j < k 的三元组 (i, j, k) 的最大值，计算公式为 (nums[i] - nums[j]) * nums[k]。如果所有三元组的值均为负，则返回 0。通过预处理前缀和后缀最大值数组，可以高效计算最大值，时间复杂度为 O(n)。
🎯
关键要点
- 给定一个整数数组，求所有满足 i < j < k 的三元组 (i, j, k) 的最大值。
- 三元组的值计算公式为 (nums[i] - nums[j]) * nums[k]。
- 如果所有三元组的值均为负，则返回 0。
- 通过预处理前缀和后缀最大值数组，可以高效计算最大值，时间复杂度为 O(n)。
- 示例1: 输入 [12,6,1,2,7]，输出 77。
- 示例2: 输入 [1,10,3,4,19]，输出 133。
- 示例3: 输入 [1,2,3]，输出 0。
- 预处理 max_left 数组，存储每个 j 之前的最大值。
- 预处理 max_right 数组，存储每个 j 之后的最大值。
- 计算每个有效 j 的三元组值，并跟踪最大值。
❓
延伸问答
如何计算三元组 (i, j, k) 的最大值？
三元组的值计算公式为 (nums[i] - nums[j]) * nums[k]，需要满足 i < j < k。
如果所有三元组的值都是负数，应该返回什么？
如果所有三元组的值均为负，则返回 0。
如何提高计算三元组最大值的效率？
通过预处理前缀和后缀最大值数组，可以高效计算最大值，时间复杂度为 O(n)。
给定数组 [12,6,1,2,7]，三元组的最大值是多少？
对于数组 [12,6,1,2,7]，三元组的最大值为 77。
如何预处理 max_left 和 max_right 数组？
max_left 数组存储每个 j 之前的最大值，max_right 数组存储每个 j 之后的最大值。
对于数组 [1,2,3]，三元组的最大值是多少？
对于数组 [1,2,3]，三元组的最大值为 0，因为唯一的三元组值为负。
➡️
