合并三元组得到目标三元组如何用贪心判断？（LeetCode 1899）

简化版

只保留不会超过目标值的三元组，然后看这些合法三元组能否分别覆盖目标的三个维度。

如果某个三元组任一维大于 target，对应维度取最大值时会越界，必须丢弃；剩下的三元组中，只要三个维度都能达到 target，就能合并出目标。

详细版

合并操作是逐维取最大值。目标是 target = [a,b,c]，那么任何参与合并的三元组都不能有某一维超过对应目标值，否则最终最大值一定超过 target，无法再变小。

过滤掉越界三元组后，问题变成：在剩下的三元组中，第一维是否有人等于 a，第二维是否有人等于 b，第三维是否有人等于 c。因为合并是逐维最大值，这三个条件可以来自不同三元组。

boolean mergeTriplets(int[][] triplets, int[] target) {
    boolean x = false, y = false, z = false;
    for (int[] t : triplets) {
        if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) continue;
        if (t[0] == target[0]) x = true;
        if (t[1] == target[1]) y = true;
        if (t[2] == target[2]) z = true;
    }
    return x && y && z;
}

完整版教学

一、先理解合并操作的单调性

三元组合并不是相加，而是每一维取最大值。例如 [2,1,3] 和 [1,4,2] 合并得到 [2,4,3]。这个操作有一个重要性质：每一维只会变大或保持不变，绝不会下降。

正因为不能下降，任何超过目标的维度都是不可逆错误。比如目标是 [2,5,3]，某个三元组是 [3,1,1]，只要选了它，第一维最大值至少是 3，永远不可能回到 2。因此贪心第一步就是过滤越界三元组。

二、为什么合法三元组可以放心使用

如果三元组每一维都 <= target，它参与合并不会让任何维度超过目标。它可能只贡献一个维度，也可能贡献多个维度；即使某些维度偏小，也不会造成负面影响，因为其他合法三元组可以继续把这些维度抬高。

这就是本题贪心很简单的原因：合法元素没有副作用，非法元素有不可逆副作用。所以对合法三元组不需要复杂选择，只要收集它们能覆盖哪些目标维度即可。

三、三个维度可以来自不同三元组

目标 [2,5,3] 可以由 [2,1,3] 和 [1,5,2] 合并得到：

max([2,1,3], [1,5,2]) = [2,5,3]

第一维和第三维来自第一个三元组，第二维来自第二个三元组。这说明不必寻找一个完全等于 target 的三元组，也不必要求某个三元组覆盖多个维度。只要每个维度至少被某个合法三元组命中，就能逐维取最大得到目标。

四、数字例子走查

设 triplets = [[2,5,3],[1,8,4],[1,5,3]]，target = [2,5,3]。

三元组	是否合法	贡献
`[2,5,3]`	合法	三维全覆盖
`[1,8,4]`	非法	第二维和第三维超过目标
`[1,5,3]`	合法	覆盖第二、三维

第一个合法三元组已经覆盖三维，所以返回 true。若没有 [2,5,3]，只靠 [1,5,3] 则第一维无法达到 2，返回 false。

五、流程图理解过滤与覆盖

遍历 triplets
   |
   |-- 任一维 > target ? -- 是 --> 丢弃
   |                         |
   |                         否
   v
检查是否命中 target[0/1/2]
   |
三个维度都命中 ? true : false

这个流程体现了两个动作：先排除会导致越界的候选，再累计安全候选提供的覆盖能力。它不是求最少选几个三元组，而是判断是否存在可合并集合。

六、和区间覆盖/集合覆盖的区别

这题看起来像集合覆盖，但比一般集合覆盖简单。普通集合覆盖中，选择某个集合可能有成本，且要优化数量；本题没有成本，合法三元组也没有负作用。因此只要看到一个维度能被合法三元组覆盖，就可以把对应标记置为 true。

记忆钩子：合并是逐维 max，超过目标不可逆；不超过目标无副作用，能覆盖几维就收几维。

七、常见误区与追问

误区：必须找到一个完全等于 target 的三元组。 三个维度可以由不同合法三元组共同覆盖。
误区：越界三元组也可以参与。 逐维最大值无法下降，越界后永远回不到目标。
误区：只检查每个维度是否出现过目标值。 必须出现在合法三元组里，越界三元组的贡献不能用。
追问：为什么合法三元组没有副作用？ 因为所有维度都不超过目标，取最大不会越界。
追问：复杂度是多少？ 遍历一次三元组，时间 O(n)，空间 O(1)。
追问：如果是 k 维数组怎么办？ 思路不变，过滤越界向量，再检查每个维度是否被合法向量覆盖。

八、加强记忆

合并三元组的核心是「max 只能升不能降」。先用这个单调性排除所有超过 target 的三元组，因为它们一旦参与就不可逆越界。剩下的三元组都是安全的，可以随便合并；只需要记录三个目标维度是否分别被命中过。记住「先过滤越界，再逐维打勾」，这题就会变成一次线性扫描。

简化版

详细版