教程文檔【免費(fèi)下載鏈接】LogicStack-LeetCode公眾號「宮水三葉的刷題日記」刷穿 LeetCode 系列文章源碼項(xiàng)目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode點(diǎn)擊查看免費(fèi)下載本文是「宮水三葉的刷題日記」倉庫中 LeetCode 1713 題解的技術(shù)深度解讀。題目要求通過任意位置插入整數(shù)使target成為arr的子序列核心難點(diǎn)在于數(shù)據(jù)規(guī)模達(dá) 10^5 時(shí)樸素 LCS 的 O(n×m) 解法必然超時(shí)。文章將完整繼承原題解的分析脈絡(luò)先抽象成最長公共子序列LCS問題再利用「target元素互不相同」這一關(guān)鍵限制將 LCS 轉(zhuǎn)換為最長上升子序列LIS最后用「維護(hù)單調(diào)序列 二分」的貪心解法把整體復(fù)雜度降到 O(n m log m)。讀完你將同時(shí)掌握兩類經(jīng)典序列問題的互相轉(zhuǎn)化技巧以及 LIS 貪心解法的嚴(yán)格正確性證明。題目描述與示例給定兩個(gè)數(shù)組target包含若干互不相同的整數(shù)arr可能包含重復(fù)元素。每一次操作中可以在arr的任意位置包括開頭與末尾插入任一整數(shù)。要求返回最少操作次數(shù)使得target成為arr的一個(gè)子序列。子序列定義刪除原數(shù)組的某些元素可以一個(gè)都不刪除且不改變其余元素相對順序后得到的數(shù)組。例如[2,7,4]是[4,2,3,7,2,1,4]的子序列而[2,4,2]不是。示例 1輸入target [5,1,3], arr [9,4,2,3,4] 輸出2 解釋添加 5 和 1使 arr 變?yōu)?[5,9,4,1,2,3,4]此時(shí) target 是 arr 的子序列。示例 2輸入target [6,4,8,1,3,2], arr [4,7,6,2,3,8,6,1] 輸出3提示1 target.length, arr.length 10^51 target[i], arr[i] 10^9target不包含任何重復(fù)元素基本分析最少操作次數(shù)與 LCS 的關(guān)系令target長度為 narr長度為 m二者**最長公共子序列LCS**長度為max。由于我們只能在arr中插入元素、不能刪除元素target成為arr子序列的充要條件是target中不在arr中按順序出現(xiàn)的那部分元素需要被插入補(bǔ)齊。換句話說已經(jīng)免費(fèi)存在的部分就是target與arr的最長公共子序列剩余 n - max 個(gè)元素必須手動插入。因此最終答案為n - max。從題面看這是一道標(biāo)準(zhǔn)的 LCS 問題樸素求解需要定義狀態(tài)f[i][j]為「考慮a數(shù)組前 i 個(gè)元素和b數(shù)組前 j 個(gè)元素的最長公共子序列長度」復(fù)雜度 O(n×m)。本題數(shù)據(jù)范圍達(dá) 10^5樸素做法必然超時(shí)。一個(gè)非常顯眼的切入點(diǎn)是target數(shù)組元素各不相同。當(dāng) LCS 問題增加其中一個(gè)數(shù)組元素互不相同的條件限制后會存在一個(gè)經(jīng)典且優(yōu)美的性質(zhì)當(dāng)其中一個(gè)數(shù)組元素各不相同時(shí)LCS 問題可以轉(zhuǎn)換為 LIS 問題求解而 LIS 問題存在「維護(hù)單調(diào)序列 二分」的貪心解法復(fù)雜度為 O(n log n)。因此本題的解題路徑是抽象成 LCS 問題利用target元素互不相同轉(zhuǎn)換為 LIS 問題使用 LIS 的貪心解法單調(diào)數(shù)組 二分做到 O(n m log m)。下面分別嚴(yán)格證明第 2 步和第 3 步的合理性與正確性。核心洞察LCS 與 LIS 的一一對應(yīng)關(guān)系本質(zhì)結(jié)論當(dāng)其中一個(gè)數(shù)組元素各不相同時(shí)每一個(gè)公共子序列都一一對應(yīng)著不重復(fù)元素?cái)?shù)組的下標(biāo)數(shù)組中的某個(gè)上升子序列反之亦然。以本題的target和arr為例由于target元素各不相同target元素與其下標(biāo)之間存在唯一映射關(guān)系將注意力集中在兩數(shù)組的公共元素上忽略非公共元素把a(bǔ)rr中的公共元素替換為它在target中的下標(biāo)此時(shí)原 LCS 問題等價(jià)于在這個(gè)下標(biāo)數(shù)組中找最長上升子序列LIS。注意示意圖只畫出了兩個(gè)數(shù)組的某個(gè)片段不要錯(cuò)誤理解為兩數(shù)組等長原題解配圖可參見倉庫文檔 1713. 得到子序列的最少操作次數(shù)困難。正向?qū)?yīng)如果存在某個(gè)公共子序列根據(jù)子序列定義它在target中的對應(yīng)下標(biāo)序列必然嚴(yán)格遞增即對應(yīng)一個(gè)上升子序列。反向?qū)?yīng)對于下標(biāo)數(shù)組的某個(gè)上升子序列其每個(gè)元素都意味著該值在target中出現(xiàn)過且出現(xiàn)順序遞增完全符合公共子序列定義即對應(yīng)一個(gè)公共子序列。由此原問題從 LCS 嚴(yán)格轉(zhuǎn)換為了 LIS轉(zhuǎn)換本身不丟失任何信息。LIS 貪心解法的正確性證明樸素 LIS 與貪心 LIS 的兩個(gè)數(shù)組樸素 LIS 需要定義動規(guī)數(shù)組ff[i]代表以nums[i]為結(jié)尾的最長上升子序列長度。計(jì)算f[i]時(shí)需要回看[0, i-1]區(qū)間內(nèi)所有滿足nums[j] nums[i]的位置 j取所有f[j] 1的最大值因此樸素 LIS 是 O(n2)。貪心解法則額外維護(hù)一個(gè)數(shù)組gf動規(guī)數(shù)組與樸素解法含義一致f[i]代表以nums[i]為結(jié)尾的上升子序列的最大長度g貪心數(shù)組g[len] x代表長度為 len 的上升子序列的「最小結(jié)尾元素」為 x。我們期望用g數(shù)組代替線性遍歷計(jì)算f[i]時(shí)需要找到滿足g[idx] nums[i]的最大下標(biāo)idx即最后一個(gè)還能接上nums[i]的位置。如果g數(shù)組單調(diào)遞增就能通過二分在 O(log n) 內(nèi)找到這個(gè)分割點(diǎn)。反證法證明 g 數(shù)組單調(diào)遞增假設(shè)存在位置 i j 使得g不滿足單調(diào)遞增只有兩種可能情況一g[i] g[j] x這意味著某個(gè)值 x 既能作為長度 i 的上升子序列的最后一位也能作為長度 j 的上升子序列的最后一位。根據(jù)定義g[i] x是所有長度為 i 的上升子序列中的最小結(jié)尾。但由于g[j] x且上升子序列必然嚴(yán)格單調(diào)我們可以刪除長度為 j 的子序列末尾若干元素構(gòu)造出一個(gè)長度為 i 的子序列得到一個(gè)新的長度為 i 的上升子序列其結(jié)尾元素嚴(yán)格小于 x這與x是長度為 i 的最小結(jié)尾矛盾。故g[i] g[j]恒不成立。情況二g[i] g[j] x同理若存在長度為 j 的合法上升子序列、其最小結(jié)尾為 x那么刪掉末尾元素必然能構(gòu)造出長度為 i 的上升子序列其結(jié)尾小于 x從而可以更新g[i]為更小的值與g[i] x矛盾。故g[i] g[j]恒不成立。根據(jù)全序關(guān)系排除了相等與大于兩種可能后只能有g(shù)[i] g[j]恒成立即g數(shù)組嚴(yán)格單調(diào)遞增。由于每個(gè)f[i]的取值在貪心做法與樸素做法中完全一致轉(zhuǎn)移來源通過單調(diào)的g數(shù)組二分確定貪心解法正確性得證。動態(tài)規(guī)劃 貪心 二分完整實(shí)現(xiàn)算法步驟建立下標(biāo)映射用哈希表map記錄target中每個(gè)元素的下標(biāo)O(n)構(gòu)造下標(biāo)數(shù)組遍歷arr只保留出現(xiàn)在target中的元素替換為其下標(biāo)得到數(shù)組listO(m)。list的長度len m貪心求 LIS維護(hù)動規(guī)數(shù)組f與貪心數(shù)組gg初始化為極大值代表長度為 0 的結(jié)尾不存在對list中每個(gè)元素在g上二分找到滿足g[mid] list[i]的最大下標(biāo)mid得到clen mid 1更新f[i] clen用g[clen] min(g[clen], list[i])維護(hù)最小結(jié)尾元素用max max(max, clen)記錄全局最長上升子序列長度輸出答案n - max。邊界情況若兩數(shù)組無公共元素list為空max 0答案為 n全部元素都需要插入若arr已按順序完整包含targetmax n答案為 0。注意元素值可達(dá) 10^9必須使用哈希表HashMap/map/字典而非按值開數(shù)組。Java 實(shí)現(xiàn)class Solution { public int minOperations(int[] t, int[] arr) { int n t.length, m arr.length; MapInteger, Integer map new HashMap(); for (int i 0; i n; i) { map.put(t[i], i); // target 元素 - 下標(biāo)唯一映射 } ListInteger list new ArrayList(); for (int i 0; i m; i) { int x arr[i]; if (map.containsKey(x)) list.add(map.get(x)); // 只保留公共元素的下標(biāo) } int len list.size(); int[] f new int[len], g new int[len 1]; Arrays.fill(g, Integer.MAX_VALUE); // g[0] 保持極大值保證 clen 至少為 1 int max 0; for (int i 0; i len; i) { int l 0, r len; // 二分查找最后一個(gè) g[mid] list[i] 的位置 while (l r) { int mid l r 1 1; // 取上中位數(shù)避免死循環(huán) if (g[mid] list.get(i)) l mid; else r mid - 1; } int clen r 1; // 以 list[i] 結(jié)尾的最長上升子序列長度 f[i] clen; g[clen] Math.min(g[clen], list.get(i)); // 維護(hù)“最小結(jié)尾元素” max Math.max(max, clen); } return n - max; } }C 實(shí)現(xiàn)class Solution { public: int minOperations(vectorint t, vectorint arr) { int n t.size(), m arr.size(); mapint, int map; for (int i 0; i n; i) { map[t[i]] i; } vectorint list; for (int i 0; i m; i) { int x arr[i]; if (map.count(x)) list.push_back(map[x]); } int len list.size(); vectorint f(len), g(len 1, numeric_limitsint::max()); int maxVal 0; for (int i 0; i len; i) { int l 0, r len; while (l r) { int mid l r 1 1; if (g[mid] list[i]) l mid; else r mid - 1; } int clen r 1; f[i] clen; g[clen] min(g[clen], list[i]); maxVal max(maxVal, clen); } return n - maxVal; } };Python 實(shí)現(xiàn)說明倉庫原文檔中 Python 與 TypeScript 代碼塊誤粘貼了 C 片段屬于文檔編輯時(shí)的復(fù)制粘貼痕跡此處按原題解算法給出可運(yùn)行的對應(yīng)語言版本。class Solution: def minOperations(self, t: List[int], arr: List[int]) - int: n, m len(t), len(arr) map_ {t[i]: i for i in range(n)} # target 元素 - 下標(biāo) list_ [map_[x] for x in arr if x in map_] # 只保留公共元素的下標(biāo) sz len(list_) f, g [0] * sz, [float(inf)] * (sz 1) # g 用正無窮初始化 maxv 0 for i in range(sz): l, r 0, sz while l r: mid l r 1 1 if g[mid] list_[i]: l mid else: r mid - 1 clen r 1 f[i] clen g[clen] min(g[clen], list_[i]) maxv max(maxv, clen) return n - maxvTypeScript 實(shí)現(xiàn)function minOperations(t: number[], arr: number[]): number { const n t.length, m arr.length; const map new Mapnumber, number(); for (let i 0; i n; i) map.set(t[i], i); const list: number[] []; for (let i 0; i m; i) { const x arr[i]; if (map.has(x)) list.push(map.get(x)!); } const sz list.length; const f new Array(sz).fill(0); const g new Array(sz 1).fill(Number.MAX_SAFE_INTEGER); let maxv 0; for (let i 0; i sz; i) { let l 0, r sz; while (l r) { const mid (l r 1) 1; if (g[mid] list[i]) l mid; else r mid - 1; } const clen r 1; f[i] clen; g[clen] Math.min(g[clen], list[i]); maxv Math.max(maxv, clen); } return n - maxv; }復(fù)雜度分析時(shí)間復(fù)雜度O(n) 建立target下標(biāo)映射O(m) 構(gòu)造映射數(shù)組list貪心求解 LIS 時(shí)每個(gè)元素一次二分為 O(len·log len) ≤ O(m·log m)。整體O(n m log m)空間復(fù)雜度映射表 O(n)list、f、g數(shù)組 O(m)整體O(n m)。對比樸素 LCS 的 O(n×m)本題通過元素互不相同 → LCS 轉(zhuǎn) LIS → 貪心二分把復(fù)雜度降到了接近線性的水平這是數(shù)據(jù)范圍 10^5 下能夠通過的關(guān)鍵。舉一反三倉庫中的關(guān)聯(lián)題目本題串聯(lián)了「最長公共子序列」「最長上升子序列」「貪心」「二分」四類知識點(diǎn)倉庫中與之配套的題解可以按圖索驥繼續(xù)深入LCS 樸素解法與狀態(tài)定義1143. 最長公共子序列中等——標(biāo)準(zhǔn)的二維 DPf[i][j]轉(zhuǎn)移方程為本題基本分析的起點(diǎn)LCS 變體1092. 最短公共超序列困難LIS 的排序 一維化技巧354. 俄羅斯套娃信封問題困難——同為困難題通過排序把二維問題化為 LIS可以對照學(xué)習(xí)降維思路LIS 的樸素序列 DP 與方案數(shù)統(tǒng)計(jì)673. 最長遞增子序列的個(gè)數(shù)中等——在f數(shù)組基礎(chǔ)上額外維護(hù)g計(jì)數(shù)數(shù)組可加深對動規(guī)數(shù)組含義的理解LIS 特例334. 遞增的三元子序列中等知識目錄本題已被收錄進(jìn) Index/序列 DP.md推薦指數(shù) 與 Index/二分.md 的分類索引中可在倉庫 Index 目錄下按 Tag 檢索同類型題目?？偨Y(jié)回顧整道題的思維鏈路最少插入次數(shù) n - 最長公共子序列長度是第一步抽象元素互不相同 → 公共子序列與下標(biāo)上升子序列一一對應(yīng)是問題轉(zhuǎn)化的鑰匙g 數(shù)組單調(diào)遞增反證法 二分定位轉(zhuǎn)移是復(fù)雜度躍遷的引擎。最終以 O(n m log m) 的復(fù)雜度解決 10^5 級別的數(shù)據(jù)完整代碼與逐條證明均可在倉庫文檔 1713. 得到子序列的最少操作次數(shù)困難 中找到對應(yīng)實(shí)現(xiàn)。贊分享教程文檔【免費(fèi)下載鏈接】LogicStack-LeetCode公眾號「宮水三葉的刷題日記」刷穿 LeetCode 系列文章源碼項(xiàng)目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode點(diǎn)擊查看免費(fèi)下載相關(guān)推薦LeetCode 1713 得到子序列的最少操作次數(shù)用 LIS 換皮題拆解「索引映射 貪心二分」套路LeetCode 1713 得到子序列的最少操作次數(shù)用 LIS 換皮題拆解「索引映射 貪心二分」套路 本篇題解以 leetcode 解題倉庫中 1713.文檔教程知識庫LeetCode最長子序列完全指南LIS與LCS問題全集解析LeetCode最長子序列完全指南LIS與LCS問題全集解析 在算法世界中子序列問題一直是面試和筆試的熱門考點(diǎn)而最長遞增子序列LIS和最長公共子序列文檔教程知識庫LogicStack-LeetCode 題解精講LeetCode 1403 非遞增順序的最小子序列——排序 貪心取最大元素LogicStack LeetCode 題解精講LeetCode 1403 非遞增順序的最小子序列——排序 貪心取最大元素 本文導(dǎo)讀 本文以《LogicS教程文檔上一篇Bruno徹底告別API測試煩惱的開源神器下一篇革命性Docker部署體驗(yàn)Dokploy v0.19.0帶來組織隔離與智能部署新范式創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考