題目描述:給定一個三元組陣列 triplets,其中 triplets[i] = [ai, bi, ci],以及一個目標三元組 target = [x, y, z]。每次操作可以選擇兩個三元組 i 和 j,並將 triplets[i] 更新為 [max(ai, aj), max(bi, bj), max(ci, cj)](取每個位置的最大值)。問是否能透過若干次操作,使得某個三元組等於 target。
解題思路:使用貪心策略。關鍵觀察是:merge 操作取每個位置的最大值,因此若某個三元組在任一位置的值超過 target 對應位置的值,則使用該三元組只會讓結果變大,永遠無法縮回 target 的值。
因此,篩選掉所有「壞的」三元組,即任一位置超過 target 的三元組(a > x || b > y || c > z)。
對於剩餘的「好的」三元組,由於每個位置的值都不超過 target,merge(取最大值)只會讓結果往 target 靠近或保持不變。對所有好的三元組取逐元素最大值,得到最終可達到的最優結果。
最後檢查此結果是否等於 target。若相等則回傳 true,否則回傳 false。
直觀理解:好的三元組不會「超過」target 的任何維度,merge 它們只會讓結果越來越接近 target。如果所有好的三元組合併後仍無法達到 target,說明缺少某個維度上能達到 target 值的三元組。
時間複雜度:O(n) — 只需線性遍歷一次所有三元組,每個三元組做常數次比較與更新。
空間複雜度:O(1) — 只使用固定數量的變數(a、b、c)來追蹤逐元素最大值,不需要額外空間。
1. Initialize result = [0, 0, 0].
2. For each triplet t in triplets:
a. If t[0] > target[0] OR t[1] > target[1] OR t[2] > target[2], skip it.
b. Otherwise, update result[i] = max(result[i], t[i]) for i in {0, 1, 2}.
3. Return result == target.暴力模擬 O(n^2):枚舉所有可能的 merge 順序,使用 BFS/DFS 嘗試所有可達狀態。由於每次 merge 是確定性的(取最大值),狀態空間有限,但複雜度高,不適合大輸入。
集合追蹤 O(n):維護三個 boolean 標誌(分別對應三個位置是否已達到 target 值),逐一檢查每個有效三元組是否能貢獻某個位置的 target 值。邏輯等價於主解法,但以標誌方式表達,稍微不同的實作風格。