Description
給定一個二維陣列
triplets（每個元素為 [a, b, c]）和一個目標target = [x, y, z]。可以選擇任意兩個 triplets 做 merge（逐位取 max）。判斷是否能透過若干次 merge 得到 target。
Example:
Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5] Output: true (選 [2,5,3] 和 [1,7,5] merge 得 [2,7,5])
Intuition#
過濾掉任一維度超過 target 的 triplet（因為 max 只會讓值變大），剩下的看能否湊齊 target 的每一維。
- Merge 操作是逐位取 max，一旦某個維度超過 target 就不可能回頭
- 所以只保留三個維度都 <= target 對應值的 triplets
- 在合法的 triplets 中，看是否每個維度都有某個 triplet 恰好等於 target 的該維度值
Approaches#
1: 暴力檢查所有子集#
- 概念: 對所有合法 triplets 的子集嘗試 merge，看是否能得到 target。
- 時間複雜度:
O(2^n)最差情況 - 空間複雜度:
O(1)
class Solution {
fun mergeTriplets(triplets: Array<IntArray>, target: IntArray): Boolean {
val valid = triplets.filter {
it[0] <= target[0] && it[1] <= target[1] && it[2] <= target[2]
}
// 嘗試所有子集
val n = valid.size
for (mask in 1 until (1 shl n)) {
val merged = intArrayOf(0, 0, 0)
for (i in 0 until n) {
if (mask and (1 shl i) != 0) {
for (k in 0..2) merged[k] = maxOf(merged[k], valid[i][k])
}
}
if (merged.contentEquals(target)) return true
}
return false
}
}⭐2: Greedy（一次遍歷）#
- 概念: 過濾合法 triplets 後，只需檢查每個維度是否存在等於 target 的值。用一個 Set 記錄哪些維度已經被滿足。
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun mergeTriplets(triplets: Array<IntArray>, target: IntArray): Boolean {
val found = BooleanArray(3)
for (t in triplets) {
if (t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2]) {
for (k in 0..2) {
if (t[k] == target[k]) found[k] = true
}
}
}
return found[0] && found[1] && found[2]
}
}🔑 Takeaways#
- Pattern: 貪心過濾 — 先排除不可能的候選者，再驗證可行性
- 關鍵技巧: merge（逐位取 max）的單調性是關鍵：值只能增不能減，所以超過 target 的 triplet 直接淘汰