# 1899. 合并若干三元组以形成目标三元组

### 题目地址(1899. 合并若干三元组以形成目标三元组)

<https://leetcode-cn.com/problems/merge-triplets-to-form-target-triplet/>

### 题目描述

```
三元组 是一个由三个整数组成的数组。给你一个二维整数数组 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 <= 105
triplets[i].length == target.length == 3
1 <= ai, bi, ci, x, y, z <= 1000
```

### 前置知识

* 贪心

### 公司

* 暂无

### 思路（贪心）

为了描述方便，我将题目中的操作`选出两个下标（下标 从 0 开始 计数）i 和 j（i != j），并 更新 triplets[j] 为 [max(ai, aj), max(bi, bj), max(ci, cj)]` 简称为 max 操作。

暴力的思路是枚举所有的可能。即枚举二元组合，接下来将 max 操作结果放回 triplets，经过这样的操作 triples 长度减少了 1。不断执行这样的 max 操作即可得到得到结果。

接下来，我们思考如下优化。

#### 要点一

首先枚举的顺序是无关的。比如先枚举 triplets\[0] 和 triplets\[1]，再将结果与 triplets\[2] 进行 max 操作。这其实等价于 triplets\[1] 和 triplets\[2]，再将结果与 triplets\[0] 进行 max 操作。

> 这其实很重要。 比如背包问题就是顺序无关的，因此就可以进行优化，而不是暴力枚举所有可能。

#### 要点二

接下来是第二个要点。即 max 操作其实是单调递增的。比如将 triplets\[0] 和 triplets\[1] 进行 max 操作，那么 max 结果(cx, cy, cz) 一定分别比 triplets\[0] 和 triplets\[1] 不比对应位置小。即：

* cx >= triplets\[0]\[0]
* cx >= triplets\[1]\[0]
* cy >= triplets\[0]\[1]
* cy >= triplets\[1]\[1]
* cz >= triplets\[0]\[2]
* cz >= triplets\[1]\[2]

这样就有一个重要性质。 比如 **当前的 max 结果是 (cx, cy, cz) 与 (x, y, z) 进行 max 操作，其中 x <= tx, y <= ty, z <= tz，一定不会比不 max 差，其中 (tx, ty, tz) 就是题目给的 target。** 这样我们可以贪心地与其进行 max 操作。如果最终 max 结果与 (tx, ty, tz) 相同，那么返回 True， 否则返回 False。

#### 要点三

还剩最后一个要点。那就是我们选择的若干 triplets 中一定不能有比 target 对应位大，这是显然的。比如 target = \[2,3,5] , 那么选择的三元组 (cx, cy, cz) 一定满足：

* cx <= 2
* cy <= 3
* cz <= 5

#### 具体算法

由于我的算法就有了，那就是**将满足要点三**的三元组全部进行 max 操作，由**要点一**知道 max 操作顺序其实是无所谓的，因此怎么遍历都行。最后将 max 结果与 target 比对即可。

### 关键点

* max 操作的**单调递增性**

### 代码

* 语言支持：Python3, CPP

Python3 Code:

```python

class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        tx, ty, tz = target
        cx = cy = cz = 0
        for a, b, c in triplets:
            if a <= tx and b <= ty and c <= tz:
                cx, cy, cz = max(cx, a), max(cy, b), max(cz, c)
        return (cx, cy, cz) == (tx, ty, tz)

```

CPP Code:

> 代码来源于网络

```cpp
class Solution {
public:
    bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
        bool sx = false, sy = false, sz = false;
        for (int i = 0; i < triplets.size() && (!sx || !sy || !sz); i++) {
            auto &t = triplets[i];
            if (t[0] == target[0] && t[1] <= target[1] && t[2] <= target[2]) {
                sx = true;
            }
            if (t[1] == target[1] && t[0] <= target[0] && t[2] <= target[2]) {
                sy = true;
            }
            if (t[2] == target[2] && t[0] <= target[0] && t[1] <= target[1]) {
                sz = true;
            }
        }
        return sx && sy && sz;
    }
};
```

**复杂度分析**

令 n 为 triplets 长度。

* 时间复杂度：$O(n)$
* 空间复杂度：$O(1)$

### 扩展

如果题目的 max 操作改成二进制位的或操作，那么会有什么不一样呢？

> 提示：或也具有单调递增性，本质和 max 操作差不多。

> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/ztxhe1.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1899.merge-triplets-to-form-target-triplet.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.