題目網址：https://leetcode.cn/problems/merge-triplets-to-form-target-triplet/

題意：triplet 是由三個整數所組成的 array。給一 2D 整數 array triplets, 其中 triplets[i] = [ai, bi, ci] 表示第 i 個 triplet。並給一整數 array target = [x, y, z], 表示你想要得到的 triplet。

為了得到 target, 你需要對 triplets 進行下面的操作任意次（也可能是 0 次）：

  • 選出兩個 index（index 從 0 開始）i 和 j（i != j）, 並更新 triplets[j] 為 [max(ai, aj), max(bi, bj), max(ci, cj)]

e.g. 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。

Solution：

想法：利用 Greedy, 令 x = target[0], y = target[1], z = target[2], 且 ai = triplet[0], bi = triplet[1], ci = triplet[2]。若 ai > x 或 bi > y 或 ci > z, 則跳過該 triplet, 因為若拿該 triplet 做運算 (a, b, c) 一定不等於 (x, y, z)。否則, 更新 a, b, c。最後判斷 (a, b, c) 是否等於 (x, y, z)

class Solution {
public:
    bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
        int a = 0, b = 0, c = 0;
        const int x = target[0], y = target[1], z = target[2];

        for (const auto& triplet : triplets) {
            const int ai = triplet[0], bi = triplet[1], ci = triplet[2];

            // 若 ai > x 或 bi > y 或 ci > z, 則跳過該 triplet
            if (ai <= x && bi <= y && ci <= z) {
                a = max(a, ai);
                b = max(b, bi);
                c = max(c, ci);
            }
        }

        // tie 可用於比較 struct
        return tie(a, b, c) == tie(x, y, z);
    }
};
  • time：$O(n)$ ➔ 遍歷 triplets
  • space：$O(1)$ ➔ 只需常數空間