LeetCode 题解工作台
合并若干三元组以形成目标三元组
三元组 是一个由三个整数组成的数组。给你一个二维整数数组 triplets ，其中 triplets[i] = [a i , b i , c i ] 表示第 i 个 三元组 。同时，给你一个整数数组 target = [x, y, z] ，表示你想要得到的 三元组 。 为了得到 target ，你需…
2
题型
7
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
我们记 $\textit{target} = [x, y, z]$，我们需要判断是否存在三元组 $[a, b, c]$ 使得 $a \le x, b \le y, c \le z$。 我们可以将所有的三元组分为两类：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
三元组 是一个由三个整数组成的数组。给你一个二维整数数组 triplets ，其中 triplets[i] = [ai, bi, ci] 表示第 i 个 三元组 。同时，给你一个整数数组 target = [x, y, z] ，表示你想要得到的 三元组 。
为了得到 target ，你需要对 triplets 执行下面的操作 任意次（可能 零 次）：
- 选出两个下标（下标 从 0 开始 计数）
i和j（i != j），并 更新triplets[j]为[max(ai, aj), max(bi, bj), max(ci, cj)]。- 例如，
triplets[i] = [2, 5, 3]且triplets[j] = [1, 7, 5]，triplets[j]将会更新为[max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5]。
- 例如，
如果通过以上操作我们可以使得目标 三元组 target 成为 triplets 的一个 元素 ，则返回 true ；否则，返回 false 。
示例 1：
输入：triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5] 输出：true 解释：执行下述操作： - 选择第一个和最后一个三元组 [[2,5,3],[1,8,4],[1,7,5]] 。更新最后一个三元组为 [max(2,1), max(5,7), max(3,5)] = [2,7,5] 。triplets = [[2,5,3],[1,8,4],[2,7,5]] 目标三元组 [2,7,5] 现在是 triplets 的一个元素。
示例 2：
输入：triplets = [[1,3,4],[2,5,8]], target = [2,5,8] 输出：true 解释：目标三元组 [2,5,8] 已经是 triplets 的一个元素。
示例 3：
输入：triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5] 输出：true 解释：执行下述操作： - 选择第一个和第三个三元组 [[2,5,3],[2,3,4],[1,2,5],[5,2,3]] 。更新第三个三元组为 [max(2,1), max(5,2), max(3,5)] = [2,5,5] 。triplets = [[2,5,3],[2,3,4],[2,5,5],[5,2,3]] 。 - 选择第三个和第四个三元组 [[2,5,3],[2,3,4],[2,5,5],[5,2,3]] 。更新第四个三元组为 [max(2,5), max(5,2), max(5,3)] = [5,5,5] 。triplets = [[2,5,3],[2,3,4],[2,5,5],[5,5,5]] 。 目标三元组 [5,5,5] 现在是 triplets 的一个元素。
示例 4：
输入：triplets = [[3,4,5],[4,5,6]], target = [3,2,5] 输出：false 解释：无法得到 [3,2,5] ，因为 triplets 不含 2 。
提示：
1 <= triplets.length <= 105triplets[i].length == target.length == 31 <= ai, bi, ci, x, y, z <= 1000
解题思路
方法一：贪心
我们记 ，我们需要判断是否存在三元组 使得 。
我们可以将所有的三元组分为两类：
- 满足 的三元组。
- 不满足 的三元组。
对于第一类三元组，我们可以将它们的 分别取最大值，得到一个新的三元组 。
对于第二类三元组，我们可以忽略它们，因为它们无法帮助我们得到目标三元组。
最后，我们只需要判断 是否等于 即可。如果等于，返回 ，否则返回 。
时间复杂度 ，其中 为数组 的长度。空间复杂度 。
class Solution:
def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
x, y, z = target
d = e = f = 0
for a, b, c in triplets:
if a <= x and b <= y and c <= z:
d = max(d, a)
e = max(e, b)
f = max(f, c)
return [d, e, f] == target
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each triplet is processed once. Space complexity is O(1) beyond input storage, using only three variables to track running maximums. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate considers which triplets actually affect the target values.
- question_mark
Candidate identifies unnecessary merges that violate the target invariant.
- question_mark
Candidate uses a greedy update to track max values efficiently.
常见陷阱
外企场景- error
Including triplets with elements exceeding the target, which breaks the invariant.
- error
Failing to track all three dimensions correctly, leading to false negatives.
- error
Attempting all merge permutations instead of using greedy selection.
进阶变体
外企场景- arrow_right_alt
Target triplet size larger than 3, generalizing the greedy merge approach.
- arrow_right_alt
Triplets contain negative numbers, requiring careful maximum computation.
- arrow_right_alt
Return the minimum number of merges needed instead of a boolean result.