Medium

题目描述

三元组是由三个整数组成的数组。给你一个二维整数数组 triplets，其中 triplets[i] = [ai, bi, ci] 描述了第 i 个三元组。同时给你一个整数数组 target = [x, y, z]，描述了你想要获得的三元组。

为了获得目标三元组，你可以对 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]。

如果通过以上操作你可以使目标三元组 [x, y, z] 成为 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 = [[3,4,5],[4,5,6]], target = [3,2,5]
输出：false
解释：无法得到 [3,2,5]，因为所有三元组中都没有 2。

示例 3:

输入：triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
输出：true

提示:

  • 1 <= triplets.length <= 10^5
  • triplets[i].length == target.length == 3
  • 1 <= ai, bi, ci, x, y, z <= 1000

解题思路

解题思路

这道题的关键是理解操作的本质：合并两个三元组时，每个位置都取最大值。因此，一旦某个三元组的任何一个位置的值超过了目标值，这个三元组就永远无法被用来构造目标三元组。

核心观察：

  1. 筛选有效三元组：只有当三元组的每个位置的值都不超过目标值时，这个三元组才可能对构造目标有用。
  2. 贪心策略：从所有有效的三元组中，我们需要找到能够覆盖目标三元组每个位置的组合。

算法步骤：

  1. 首先过滤掉所有"坏"的三元组（任何位置超过目标值的三元组）
  2. 对于剩余的"好"三元组，检查它们是否能够组合出目标三元组
  3. 具体来说，我们需要确保对于目标的每个位置，都存在至少一个好三元组在该位置上等于目标值

这种方法的正确性在于：如果存在好三元组能覆盖目标的所有位置，那么通过不断取最大值的操作，我们一定能构造出目标三元组。

推荐解法：贪心算法，时间复杂度O(n)，空间复杂度O(1)。

代码实现

class Solution {
public:
    bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
        vector<bool> good(3, false);
        
        for (auto& triplet : triplets) {
            // 检查是否为"好"三元组（每个位置都不超过目标值）
            if (triplet[0] <= target[0] && triplet[1] <= target[1] && triplet[2] <= target[2]) {
                // 标记能匹配目标值的位置
                for (int i = 0; i < 3; i++) {
                    if (triplet[i] == target[i]) {
                        good[i] = true;
                    }
                }
            }
        }
        
        // 检查是否所有位置都能被覆盖
        return good[0] && good[1] && good[2];
    }
};

class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        good = [False] * 3
        
        for triplet in triplets:
            # 检查是否为"好"三元组
            if all(triplet[i] <= target[i] for i in range(3)):
                # 标记能匹配目标值的位置
                for i in range(3):
                    if triplet[i] == target[i]:
                        good[i] = True
        
        # 检查是否所有位置都能被覆盖
        return all(good)

public class Solution {
    public bool MergeTriplets(int[][] triplets, int[] target) {
        bool[] good = new bool[3];
        
        foreach (int[] triplet in triplets) {
            // 检查是否为"好"三元组
            if (triplet[0] <= target[0] && triplet[1] <= target[1] && triplet[2] <= target[2]) {
                // 标记能匹配目标值的位置
                for (int i = 0; i < 3; i++) {
                    if (triplet[i] == target[i]) {
                        good[i] = true;
                    }
                }
            }
        }
        
        // 检查是否所有位置都能被覆盖
        return good[0] && good[1] && good[2];
    }
}

var mergeTriplets = function(triplets, target) {
    let canReach = [false, false, false];
    
    for (let triplet of triplets) {
        if (triplet[0] <= target[0] && triplet[1] <= target[1] && triplet[2] <= target[2]) {
            if (triplet[0] === target[0]) canReach[0] = true;
            if (triplet[1] === target[1]) canReach[1] = true;
            if (triplet[2] === target[2]) canReach[2] = true;
        }
    }
    
    return canReach[0] && canReach[1] && canReach[2];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

其中 n 是三元组的数量。我们只需要遍历一次所有三元组，每个三元组的处理时间为常数，因此总时间复杂度为 O(n)。空间复杂度为 O(1)，因为我们只使用了固定大小的辅助数组。