教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本文是「宫水三叶的刷题日记」仓库中 LeetCode 1713 题解的技术深度解读。题目要求通过任意位置插入整数使target成为arr的子序列核心难点在于数据规模达 10^5 时朴素 LCS 的 O(n×m) 解法必然超时。文章将完整继承原题解的分析脉络先抽象成最长公共子序列LCS问题再利用「target元素互不相同」这一关键限制将 LCS 转换为最长上升子序列LIS最后用「维护单调序列 二分」的贪心解法把整体复杂度降到 O(n m log m)。读完你将同时掌握两类经典序列问题的互相转化技巧以及 LIS 贪心解法的严格正确性证明。题目描述与示例给定两个数组target包含若干互不相同的整数arr可能包含重复元素。每一次操作中可以在arr的任意位置包括开头与末尾插入任一整数。要求返回最少操作次数使得target成为arr的一个子序列。子序列定义删除原数组的某些元素可以一个都不删除且不改变其余元素相对顺序后得到的数组。例如[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 变为 [5,9,4,1,2,3,4]此时 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不包含任何重复元素基本分析最少操作次数与 LCS 的关系令target长度为 narr长度为 m二者**最长公共子序列LCS**长度为max。由于我们只能在arr中插入元素、不能删除元素target成为arr子序列的充要条件是target中不在arr中按顺序出现的那部分元素需要被插入补齐。换句话说已经免费存在的部分就是target与arr的最长公共子序列剩余 n - max 个元素必须手动插入。因此最终答案为n - max。从题面看这是一道标准的 LCS 问题朴素求解需要定义状态f[i][j]为「考虑a数组前 i 个元素和b数组前 j 个元素的最长公共子序列长度」复杂度 O(n×m)。本题数据范围达 10^5朴素做法必然超时。一个非常显眼的切入点是target数组元素各不相同。当 LCS 问题增加其中一个数组元素互不相同的条件限制后会存在一个经典且优美的性质当其中一个数组元素各不相同时LCS 问题可以转换为 LIS 问题求解而 LIS 问题存在「维护单调序列 二分」的贪心解法复杂度为 O(n log n)。因此本题的解题路径是抽象成 LCS 问题利用target元素互不相同转换为 LIS 问题使用 LIS 的贪心解法单调数组 二分做到 O(n m log m)。下面分别严格证明第 2 步和第 3 步的合理性与正确性。核心洞察LCS 与 LIS 的一一对应关系本质结论当其中一个数组元素各不相同时每一个公共子序列都一一对应着不重复元素数组的下标数组中的某个上升子序列反之亦然。以本题的target和arr为例由于target元素各不相同target元素与其下标之间存在唯一映射关系将注意力集中在两数组的公共元素上忽略非公共元素把arr中的公共元素替换为它在target中的下标此时原 LCS 问题等价于在这个下标数组中找最长上升子序列LIS。注意示意图只画出了两个数组的某个片段不要错误理解为两数组等长原题解配图可参见仓库文档 1713. 得到子序列的最少操作次数困难。正向对应如果存在某个公共子序列根据子序列定义它在target中的对应下标序列必然严格递增即对应一个上升子序列。反向对应对于下标数组的某个上升子序列其每个元素都意味着该值在target中出现过且出现顺序递增完全符合公共子序列定义即对应一个公共子序列。由此原问题从 LCS 严格转换为了 LIS转换本身不丢失任何信息。LIS 贪心解法的正确性证明朴素 LIS 与贪心 LIS 的两个数组朴素 LIS 需要定义动规数组ff[i]代表以nums[i]为结尾的最长上升子序列长度。计算f[i]时需要回看[0, i-1]区间内所有满足nums[j] nums[i]的位置 j取所有f[j] 1的最大值因此朴素 LIS 是 O(n²)。贪心解法则额外维护一个数组gf动规数组与朴素解法含义一致f[i]代表以nums[i]为结尾的上升子序列的最大长度g贪心数组g[len] x代表长度为 len 的上升子序列的「最小结尾元素」为 x。我们期望用g数组代替线性遍历计算f[i]时需要找到满足g[idx] nums[i]的最大下标idx即最后一个还能接上nums[i]的位置。如果g数组单调递增就能通过二分在 O(log n) 内找到这个分割点。反证法证明 g 数组单调递增假设存在位置 i j 使得g不满足单调递增只有两种可能情况一g[i] g[j] x这意味着某个值 x 既能作为长度 i 的上升子序列的最后一位也能作为长度 j 的上升子序列的最后一位。根据定义g[i] x是所有长度为 i 的上升子序列中的最小结尾。但由于g[j] x且上升子序列必然严格单调我们可以删除长度为 j 的子序列末尾若干元素构造出一个长度为 i 的子序列得到一个新的长度为 i 的上升子序列其结尾元素严格小于 x这与x是长度为 i 的最小结尾矛盾。故g[i] g[j]恒不成立。情况二g[i] g[j] x同理若存在长度为 j 的合法上升子序列、其最小结尾为 x那么删掉末尾元素必然能构造出长度为 i 的上升子序列其结尾小于 x从而可以更新g[i]为更小的值与g[i] x矛盾。故g[i] g[j]恒不成立。根据全序关系排除了相等与大于两种可能后只能有g[i] g[j]恒成立即g数组严格单调递增。由于每个f[i]的取值在贪心做法与朴素做法中完全一致转移来源通过单调的g数组二分确定贪心解法正确性得证。动态规划 贪心 二分完整实现算法步骤建立下标映射用哈希表map记录target中每个元素的下标O(n)构造下标数组遍历arr只保留出现在target中的元素替换为其下标得到数组listO(m)。list的长度len m贪心求 LIS维护动规数组f与贪心数组gg初始化为极大值代表长度为 0 的结尾不存在对list中每个元素在g上二分找到满足g[mid] list[i]的最大下标mid得到clen mid 1更新f[i] clen用g[clen] min(g[clen], list[i])维护最小结尾元素用max max(max, clen)记录全局最长上升子序列长度输出答案n - max。边界情况若两数组无公共元素list为空max 0答案为 n全部元素都需要插入若arr已按顺序完整包含targetmax n答案为 0。注意元素值可达 10^9必须使用哈希表HashMap/map/字典而非按值开数组。Java 实现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 元素 - 下标唯一映射 } ListInteger list new ArrayList(); for (int i 0; i m; i) { int x arr[i]; if (map.containsKey(x)) list.add(map.get(x)); // 只保留公共元素的下标 } 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[mid] list[i] 的位置 while (l r) { int mid l r 1 1; // 取上中位数避免死循环 if (g[mid] list.get(i)) l mid; else r mid - 1; } int clen r 1; // 以 list[i] 结尾的最长上升子序列长度 f[i] clen; g[clen] Math.min(g[clen], list.get(i)); // 维护“最小结尾元素” max Math.max(max, clen); } return n - max; } }C 实现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 实现说明仓库原文档中 Python 与 TypeScript 代码块误粘贴了 C 片段属于文档编辑时的复制粘贴痕迹此处按原题解算法给出可运行的对应语言版本。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 元素 - 下标 list_ [map_[x] for x in arr if x in map_] # 只保留公共元素的下标 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 实现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; }复杂度分析时间复杂度O(n) 建立target下标映射O(m) 构造映射数组list贪心求解 LIS 时每个元素一次二分为 O(len·log len) ≤ O(m·log m)。整体O(n m log m)空间复杂度映射表 O(n)list、f、g数组 O(m)整体O(n m)。对比朴素 LCS 的 O(n×m)本题通过元素互不相同 → LCS 转 LIS → 贪心二分把复杂度降到了接近线性的水平这是数据范围 10^5 下能够通过的关键。举一反三仓库中的关联题目本题串联了「最长公共子序列」「最长上升子序列」「贪心」「二分」四类知识点仓库中与之配套的题解可以按图索骥继续深入LCS 朴素解法与状态定义1143. 最长公共子序列中等——标准的二维 DPf[i][j]转移方程为本题基本分析的起点LCS 变体1092. 最短公共超序列困难LIS 的排序 一维化技巧354. 俄罗斯套娃信封问题困难——同为困难题通过排序把二维问题化为 LIS可以对照学习降维思路LIS 的朴素序列 DP 与方案数统计673. 最长递增子序列的个数中等——在f数组基础上额外维护g计数数组可加深对动规数组含义的理解LIS 特例334. 递增的三元子序列中等知识目录本题已被收录进 Index/序列 DP.md推荐指数 与 Index/二分.md 的分类索引中可在仓库 Index 目录下按 Tag 检索同类型题目。总结回顾整道题的思维链路最少插入次数 n - 最长公共子序列长度是第一步抽象元素互不相同 → 公共子序列与下标上升子序列一一对应是问题转化的钥匙g 数组单调递增反证法 二分定位转移是复杂度跃迁的引擎。最终以 O(n m log m) 的复杂度解决 10^5 级别的数据完整代码与逐条证明均可在仓库文档 1713. 得到子序列的最少操作次数困难 中找到对应实现。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LeetCode 1713 得到子序列的最少操作次数用 LIS 换皮题拆解「索引映射 贪心二分」套路LeetCode 1713 得到子序列的最少操作次数用 LIS 换皮题拆解「索引映射 贪心二分」套路 本篇题解以 leetcode 解题仓库中 1713.文档教程知识库LeetCode最长子序列完全指南LIS与LCS问题全集解析LeetCode最长子序列完全指南LIS与LCS问题全集解析 在算法世界中子序列问题一直是面试和笔试的热门考点而最长递增子序列LIS和最长公共子序列文档教程知识库LogicStack-LeetCode 题解精讲LeetCode 1403 非递增顺序的最小子序列——排序 贪心取最大元素LogicStack LeetCode 题解精讲LeetCode 1403 非递增顺序的最小子序列——排序 贪心取最大元素 本文导读 本文以《LogicS教程文档上一篇Bruno彻底告别API测试烦恼的开源神器下一篇革命性Docker部署体验Dokploy v0.19.0带来组织隔离与智能部署新范式创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考