合并三元组以形成目标三元组 图解题解

这道题到底在问能不能拼出 target

给一个三元组数组 triplets 和目标三元组 target，长度都是 3。每次挑两个三元组，把其中一个换成两者在每一位上各取较大值的结果，问反复操作能否让某个三元组恰好变成 target。题面给的 target ＝ [5,5,5]，triplets ＝ [[2,5,3],[1,8,4],[1,3,5],[4,1,5],[5,2,3]]，答案是 true；拼得出返回 true，拼不出返回 false。

模拟两两合并这条路走得通吗

看到‘每次合并两个’，容易想着照操作一步步模拟：先合哪两个、再合哪两个，把配对顺序试一遍。可顺序有指数种，铺开会直接爆掉。而逐位取最大满足交换律和结合律——先合谁后合谁、合几次，最后落在某一位上的值，都等于参与进来的三元组在这一位上的最大值。顺序既然无所谓，就不必真去演具体配对。

哪些三元组能用，哪些碰都不能碰

逐位取最大只会把数往大抬、绝不调小——某一位一旦被顶上去，后面再合别的也压不回来。麻烦就出在‘超标’：一个三元组只要有某一位 ＞ target 对应那位，并进来后那一位就会冲过目标且再降不回去，结果必然对不上。所以能安全参与的，只有三位都 ≤ target 的三元组，任意一位越界就直接跳过。剩下的安全三元组逐位取最大，攒进一个 best，也就是从 [0,0,0] 起、逐位记着眼下最大值的三元组。这就是这道题的贪心：不纠结拿哪两个去配，只认这一位能不能安全抬到位。

写出来就三步：过滤、取最大、判相等

落到代码上就三件事：遍历每个三元组，逐位和 target 比，某一位 ＞ target 就跳过；对留下的安全三元组，把 best 的每一位更新成它和这个三元组在该位上的较大值；扫完判断 best 是不是恰好等于 target。最容易松手的是最后这步——超标的都滤掉了，best 每一位都 ≤ target，所以不能用‘每一位都 ≥ target’这种覆盖式判断，那样没攒够的也会算成功；要的是逐位相等，best ＝ target 才返回 true。

[5,5,5] 这个目标，best 怎么顶上去

target ＝ [5,5,5]，best 从 [0,0,0] 起。[2,5,3] 三位都不超 5，安全，best ＝ [2,5,3]。[1,8,4] 中间那位 8 ＞ 5 越界，跳过，best 不动。[1,3,5] 安全，末位被 5 顶起，best ＝ [2,5,5]。[4,1,5] 安全，首位被 4 抬高，best ＝ [4,5,5]。[5,2,3] 安全，首位被 5 顶满，best ＝ [5,5,5]。扫完 best 和 target 一位不差，返回 true。

两个地方一手滑，答案就反了

第一个坑是没过滤就把所有三元组一股脑逐位取最大——混进一个某位超标的，那位当场冲破 target 且降不回来，结果直接错。第二个坑是最后拿‘best 每位都 ≥ target’判成功，可 best 不可能超过 target，没攒够的那位其实小于 target，覆盖式判断会放它过去，必须判 best 和 target 每位相等。

Python

def mergeTriplets(triplets, target):
    best = [0, 0, 0]                 # 逐位攒到的最大
    for t in triplets:
        if all(t[j] <= target[j]     # 每一位都不超目标
               for j in range(3)):   # 才算安全三元组
            for j in range(3):
                best[j] = max(best[j], t[j])  # 逐位取最大
    return best == target            # 攒完是否正好等于目标

C++

bool mergeTriplets(vector<vector<int>>& tr, vector<int>& tg){
    vector<int> best(3, 0);
    for (auto& t : tr) {
        if (t[0]<=tg[0] && t[1]<=tg[1] && t[2]<=tg[2])
            for (int j = 0; j < 3; j++)
                best[j] = max(best[j], t[j]);
    }
    return best == tg;
}

Java

public boolean mergeTriplets(int[][] tr, int[] tg) {
    int[] best = new int[3];
    for (int[] t : tr) {
        if (t[0]<=tg[0] && t[1]<=tg[1] && t[2]<=tg[2])
            for (int j = 0; j < 3; j++)
                best[j] = Math.max(best[j], t[j]);
    }
    return best[0]==tg[0] && best[1]==tg[1] && best[2]==tg[2];
}