DEV Community
·
2873. 有序三元组的最大值 I
💡
原文英文，约700词，阅读约需3分钟。
📝
内容提要
给定一个整数数组，求所有满足 i < j < k 的三元组 (i, j, k) 的最大值，计算公式为 (nums[i] - nums[j]) * nums[k]。若所有三元组值为负，则返回 0。通过预计算每个 j 后的最大值，可以将时间复杂度从 O(n^3) 降至 O(n^2)。
🎯
关键要点
-
给定一个整数数组，求所有满足 i < j < k 的三元组 (i, j, k) 的最大值。
-
三元组的值计算公式为 (nums[i] - nums[j]) * nums[k]。
-
若所有三元组值为负，则返回 0。
-
通过预计算每个 j 后的最大值，可以将时间复杂度从 O(n^3) 降至 O(n^2)。
-
创建一个 max_right 数组，存储从 j+1 到数组末尾的最大值。
-
对于每个有效的 (i, j) 对，使用 max_right 数组计算三元组的值。
-
跟踪所有有效三元组获得的最大值，如果最大值非正，则返回 0；否则返回最大值。
❓
延伸问答
如何计算三元组的最大值？
三元组的最大值通过公式 (nums[i] - nums[j]) * nums[k] 计算，满足条件 i < j < k。
如果所有三元组的值都是负数，应该返回什么？
如果所有三元组的值为负，则返回 0。
如何优化三元组的计算时间复杂度？
通过预计算每个 j 后的最大值，可以将时间复杂度从 O(n^3) 降至 O(n^2)。
max_right 数组的作用是什么？
max_right 数组存储从 j+1 到数组末尾的最大值，帮助快速计算三元组的值。
给定数组 [12,6,1,2,7] 的最大三元组值是多少？
最大三元组值为 77。
如何实现这个算法？
可以通过创建 max_right 数组并迭代有效的 (i, j) 对来实现该算法。
➡️
