LeetCode 1899中等贪心
合并三元组以形成目标三元组 图解题解
这道题到底在问什么
可对三元组按位取 max，判断能否合成 target。
- 示例
- triplets=[[2,5,3],[1,8,4],[1,7,5]], target=[2,7,5] → true
最优解：一步一步想明白
- 3看到某一位等于 target 就直接收下，会被其它位超标污染。
- 4只用每一位都不超过 target 的三元组，再看三个位是否都能被覆盖。
- 5核心：合并逐位取 max，越合越大，只能用不超标的三元组。
- 6可用三元组才看它命中 target 的哪一位。
- 7有一位超标，整条作废 —— 这是最关键的判定。
- 8不同位可以来自不同三元组。
- 9每位都有人精确等于 target，合并即得目标。
- 12一句话记住：只用每一位都不超过 target 的三元组，再看三个位是否都能被覆盖。
- 15判定看整条、不看单位：一位超标，全条不能用。
- 22这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=greedy 连刷同类题；卡住时用 AI 答疑问“为什么整条超标就不能用”。
⚠️ 容易写错的地方
✗ 错：看到某位 == target[i] 就收下该三元组
✓ 对：必须整条三位都 ≤ target 才可用
某一位超标的三元组合并进来会把那位顶超目标，且逐位取 max 不可逆。
✗ 错：真的去模拟合并、反复比较结果
✓ 对：只记录三个位是否被「可用三元组」精确命中
可用三元组逐位 ≤ target，合并只会让各位变大但不超 target，所以每位都有人精确 == target 即可。
✗ 错：要求同一个三元组凑齐多位
✓ 对：不同位可来自不同三元组
可合并任意多个可用三元组，各位的 target 值能分别由不同三元组提供。
完整代码（Python / C++ / Java）
Python
class Solution:
def mergeTriplets(self, triplets, target):
good = [False, False, False]
for tri in triplets:
if all(tri[i] <= target[i] for i in range(3)):
for i in range(3):
if tri[i] == target[i]:
good[i] = True
return all(good)C++
class Solution {
public:
bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
vector<int> good(3);
for (auto& t : triplets) {
if (t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2]) {
for (int i=0;i<3;i++) if (t[i] == target[i]) good[i] = 1;
}
}
return good[0] && good[1] && good[2];
}
};Java
class Solution {
public boolean mergeTriplets(int[][] triplets, int[] target) {
boolean[] good = new boolean[3];
for (int[] t : triplets) {
if (t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2]) {
for (int i=0;i<3;i++) if (t[i] == target[i]) good[i] = true;
}
}
return good[0] && good[1] && good[2];
}
}套路模板 · 逐位取 max 贪心骨架
# 合并三元组（逐位取 max）骨架
good = [False, False, False]
for a, b, c in triplets:
if a <= target[0] and b <= target[1] and c <= target[2]: # 整条可用
if a == target[0]: good[0] = True
if b == target[1]: good[1] = True
if c == target[2]: good[2] = True
return all(good) # 三位都被精确命中复杂度
时间复杂度
O(n)
扫一遍所有三元组，每条 O(1) 判定
空间复杂度
O(1)
只用 3 个布尔标记位是否凑到
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 合并三元组以形成目标三元组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
整体思路是什么？+
遍历每个三元组：若它三位都 ≤ target(可用)，则看它哪些位精确等于 target，把对应位标记为「已凑到」。扫完后若三个位都被标记 → true，否则 false。
这道题为什么用「贪心」，换最直接的暴力解会差在哪？+
贪心抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。