穿上衣服我就不认识你了——最长上升子序列LIS套路全解【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读最长上升子序列Longest Increasing SubsequenceLIS是动态规划领域最经典的入门题型之一但出题人从不直接考它无重叠区间、最长数对链、引爆气球、堆箱子、俄罗斯套娃信封……这些看似八竿子打不着的题目本质上都是 LIS 的「换皮」。本文以仓库 selected/LIS.md 为主干逐题拆解 LIS 的动态规划建模过程再给出O(N log N)的贪心 二分优化并辅以仓库内 673. 最长递增子序列的个数、1713. 得到子序列的最少操作次数 等题解作为延伸证据帮你建立「透过现象看套路」的抽象思维读完本文你能识别并秒杀绝大多数 LIS 变种题。注意本文的目的是帮助你识别套路、从横向上理清解题思维框架并未采用最优解——文中给出的解法均可通过全部测试用例但并非每题的最优实现。想看更优解的读者可以自行查阅讨论区。300. 最长上升子序列LIS 本体题目描述给定一个无序的整数数组找到其中最长上升子序列的长度。示例输入:[10,9,2,5,3,7,101,18]输出:4解释: 最长的上升子序列是[2,3,7,101]它的长度是 4。说明可能会有多种最长上升子序列的组合你只需要输出对应的长度即可算法的时间复杂度应该为O(n²)进阶你能将算法的时间复杂度降低到O(n log n)吗思路两种状态定义选更可写的一种题目的意思是从给定数组中挑选若干数字这些数字满足「如果i j则nums[i] nums[j]」问一次最多可以挑选多少个满足条件的数字。这种「子序列求极值」的题目应当优先考虑贪心或动态规划。本题贪心不可行贪心无法回溯调整已做出的选择因此考虑动态规划。按照动态规划定义状态的套路有两种常见的定义方式dp[i]以i结尾一定包括i所能形成的最长上升子序列长度答案是max(dp[i])其中i 0, 1, 2, ..., n - 1dp[i]以i结尾可能包括i所能形成的最长上升子序列长度答案是dp[-1]-1 表示最后一个元素。第二种定义方式虽然无需比较不同的dp[i]就能直接获得答案看起来更方便但它的状态转移方程很不好写——因为dp[i]的末尾数字即最大的那个数可能是任意j i位置的元素无法唯一确定转移来源。这与仓库 thinkings/dynamic-programming.md 中讨论的状态定义困境一致状态定义一旦含糊转移方程就会难以确定。因此我们选择第一种建模方式。第一种方式虽然需要在循环时顺便比较不同的dp[i]来更新答案但对复杂度没有影响只是代码多几行而已。状态转移方程推导由于dp[j]中一定会包括j且以j结尾那么nums[j]一定是dp[j]所形成序列中的最大元素。若位于其后意味着i j的nums[i] nums[j]那么nums[i]一定能够融入dp[j]形成的序列从而构成一个更长的上升子序列其长度为dp[j] 1。于是状态转移方程为dp[i] max(dp[j] 1)其中 i j 且 nums[i] nums[j]以[10, 9, 2, 5, 3, 7, 101, 18]为例当计算到dp[5]对应元素 7时需要回头与位置 0、1、2、3、4 的元素逐一比较与dp[0]10比较7 10不成立跳过与dp[1]9比较7 9不成立跳过与dp[2]2比较7 2成立dp[5] max(1, dp[2] 1) 2与dp[3]5比较7 5成立dp[5] max(2, dp[3] 1) 3与dp[4]3比较7 3成立dp[5] max(3, dp[4] 1) 3。最后从所有候选中选出最大的一个加 1 赋给dp[5]即可。记住这个状态转移方程后面所有换皮题都会反复用到它。代码实现class Solution: def lengthOfLIS(self, nums: List[int]) - int: n len(nums) if n 0: return 0 dp [1] * n ans 1 for i in range(n): for j in range(i): if nums[i] nums[j]: dp[i] max(dp[i], dp[j] 1) ans max(ans, dp[i]) return ans复杂度分析时间复杂度O(N²)双层循环每对(i, j)比较一次空间复杂度O(N)一个长度n的dp数组。435. 无重叠区间删除变成「保留最长」题目描述给定一个区间的集合找到需要移除区间的最小数量使剩余区间互不重叠。注意可以认为区间的终点总是大于它的起点区间[1,2]和[2,3]的边界相互“接触”但没有相互重叠。示例 1输入[[1,2],[2,3],[3,4],[1,3]]输出1解释移除[1,3]后剩下的区间没有重叠。示例 2输入[[1,2],[1,2],[1,2]]输出2解释需要移除两个[1,2]来使剩下的区间没有重叠。示例 3输入[[1,2],[2,3]]输出0解释不需要移除任何区间因为它们已经无重叠。思路把区间看成「数字序列」先来看最终剩下的区间。由于剩下的区间互不重叠因此剩下的相邻区间的后一个区间的开始时间一定不小于前一个区间的结束时间。例如剩下的区间是[[1,2],[2,3],[3,4]]第一个区间的结束 2 小于等于第二个区间的开始 2第二个区间的结束 3 小于等于第三个区间的开始 3。不难发现如果把「前面区间的结束」和「后面区间的开始」结合起来看剩余区间序列就是一个非严格递增序列。而我们的目标正是删除若干区间从而剩下最长的非严格递增子序列。这不就是 300 题吗只不过 300 题要求严格递增这里允许相等——改一个符号变而已。反过来看300 题可以理解为「删除了若干数字剩下最长的严格递增子序列」。这就是抽象的力量这就是套路。由于要按序比较区间的「结束」与「开始」我们需要先对区间按起点或终点排序之后就转化为上面的最长递增子序列问题。与 300 题不同的是区间比较时拿后面的开始时间和前面的结束时间比较。还需要注意两点转化题目求的是需要移除的区间数量因此最后return时要做一个转化n - max(dp)题目不是要求严格递增而是可以相等因此判断条件要加上等号。这道题还有一种贪心解法效率优于动态规划但与本文主题不一致这里不再展开。代码实现你看代码多像class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) - int: n len(intervals) if n 0: return 0 dp [1] * n ans 1 intervals.sort(keylambda a: a[0]) for i in range(len(intervals)): for j in range(i - 1, -1, -1): if intervals[i][0] intervals[j][1]: dp[i] max(dp[i], dp[j] 1) break # 由于是按照开始时间排序的, 因此可以剪枝 return n - max(dp)复杂度分析时间复杂度O(N²)双层循环排序另计O(N log N)空间复杂度O(N)。646. 最长数对链去掉等号去掉转化题目描述给出n个数对。在每一个数对中第一个数字总是比第二个数字小。现在定义一种跟随关系当且仅当b c时数对(c, d)才可以跟在(a, b)后面。我们用这种形式来构造一个数对链。给定一个对数集合找出能够形成的最长数对链的长度。你不需要用到所有的数对可以以任何顺序选择其中的一些数对来构造。示例输入[[1,2],[2,3],[3,4]]输出2解释最长的数对链是[1,2] - [3,4]。注意给出数对的个数在[1, 1000]范围内。思路换皮只换了两处和上面的「435. 无重叠区间」是换皮题唯一的区别是这里又变成了严格递增b c。没关系我们把等号去掉改回就行了。并且这道题求解的是最长链的长度不是移除数量因此最后的n - max(dp)转化也不需要了直接返回max(dp)即可。当然这道题也有贪心解法效率优于动态规划与本文主题不一致这里不再展开。代码实现这代码更像了class Solution: def findLongestChain(self, intervals: List[List[int]]) - int: n len(intervals) if n 0: return 0 dp [1] * n ans 1 intervals.sort(keylambda a: a[0]) for i in range(len(intervals)): for j in range(i - 1, -1, -1): if intervals[i][0] intervals[j][1]: dp[i] max(dp[i], dp[j] 1) break # 由于是按照开始时间排序的, 因此可以剪枝 return max(dp)复杂度分析时间复杂度O(N²)空间复杂度O(N)。452. 用最少数量的箭引爆气球重叠也能算「不重叠」题目描述在二维空间中有许多球形的气球。对于每个气球输入是水平方向上气球直径的开始和结束坐标。由于它是水平的y 坐标并不重要只要知道开始和结束的 x 坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在 10⁴ 个气球。一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标x处射出一支箭若一个气球的直径开始和结束坐标为xstart, xend且满足xstart ≤ x ≤ xend则该气球会被引爆。可以射出的弓箭数量没有限制弓箭一旦射出可以无限前进。我们想找到使得所有气球全部被引爆所需弓箭的最小数量。示例输入[[10,16],[2,8],[1,6],[7,12]]输出2。解释可以在x 6射爆[2,8]、[1,6]两个气球在x 11射爆另外两个气球。思路重叠与「链」的等价把气球看成区间需要几支箭才能全部射爆意思就是这些区间能分成多少组互不相交不重叠的层——一支箭只能穿过互相重叠的气球。换句话说答案等价于「最多有多少个两两不重叠的区间」因为每组重叠的气球需要一支箭而不重叠的区间必然分属不同支箭。注意这里重叠的情况包括边界接触也能被同一支箭射爆即条件是xstart ≤ x ≤ xend。这么一抽象它就与上面的「646. 最长数对链」一模一样了——都是求「最多能选出多少个互不重叠或首尾衔接的区间」直接套用即可不用多说了吧这道题同样有更高效的贪心解法与本文主题不一致不再展开。代码实现代码像不像class Solution: def findMinArrowShots(self, intervals: List[List[int]]) - int: n len(intervals) if n 0: return 0 dp [1] * n ans 1 intervals.sort(keylambda a: a[0]) for i in range(len(intervals)): for j in range(i - 1, -1, -1): if intervals[i][0] intervals[j][1]: dp[i] max(dp[i], dp[j] 1) break # 由于是按照开始时间排序的, 因此可以剪枝 return max(dp)复杂度分析时间复杂度O(N²)空间复杂度O(N)。优化贪心 二分把 LIS 做到 O(N log N)上面的 DP 解法虽然思路清晰但O(N²)在处理10⁵量级的数据时会超时。LIS 也可以用贪心 二分达到O(N log N)的优良效率代码如下class Solution: def lengthOfLIS(self, A: List[int]) - int: d [] for a in A: i bisect.bisect_left(d, a) if i len(d): d[i] a elif not d or d[-1] a: d.append(a) return len(d)核心思想维护一个数组d其中d[k]表示「长度为k1的上升子序列的最小末尾值」。贪心在于末尾值越小越有利于后续元素接上去形成更长的序列。每来一个新元素a用二分bisect_left找到它在d中的插入位置若位置在数组内部则用a替换该位置的值因为a更小作为该长度的新末尾更优若位置超出数组末尾且a大于当前末尾则追加序列可以更长。最终len(d)就是 LIS 的长度。关于bisect_left/bisect_right的语义细节可参见仓库的二分专题 91/binary-search.md 与 thinkings/binary-search-2.md。变体最长不递减子序列如果求的是最长不递减子序列允许相等呢只需要把最左插入改为最右插入即可bisect_left改为bisect即bisect_right同时把追加条件的小于号改为小于等于号class Solution: def lengthOfLIS(self, A: List[int]) - int: d [] for a in A: # 这里改为最右 i bisect.bisect(d, a) if i len(d): d[i] a # 这里改为小于等号 elif not d or d[-1] a: d.append(a) return len(d)也可以写得更简洁一些def LIS(A): d [] for a in A: # 如果要求严格递增就改为最左插入 bisect_left 即可 i bisect.bisect(d, a) if i len(d): d.append(a) elif d[i] ! a: d[i] a return len(d)最左插入bisect_left与最右插入bisect_right分不清的读者可以看看仓库中的二分专题 thinkings/binary-search-2.md。More一网打尽 LIS 换皮题套路讲到这里剩下的就是「套模板」的环节了。以下题目在仓库中均有对应题解或可作为练习673. 最长递增子序列的个数滴滴面试题不就是先求出最长序列长度之后再循环比对一次就可以得出答案了么难点在于除了长度还要同步维护个数。仓库 problems/673.number-of-longest-increasing-subsequence.md 给出了完整推导用dp[i][0]表示以nums[i]结尾的 LIS 长度dp[i][1]表示该长度的子序列个数转移时「变长则继承个数、等长则累加个数」class Solution: def findNumberOfLIS(self, nums: List[int]) - int: n len(nums) # dp[i][0] - LIS # dp[i][1] - NumberOfLIS dp [[1, 1] for _ in range(n)] longest 1 for i in range(n): for j in range(i 1, n): if nums[j] nums[i]: if dp[i][0] 1 dp[j][0]: dp[j][0] dp[i][0] 1 # 下面这行代码容易忘记导致出错 dp[j][1] dp[i][1] longest max(longest, dp[j][0]) elif dp[i][0] 1 dp[j][0]: dp[j][1] dp[i][1] return sum(dp[i][1] for i in range(n) if dp[i][0] longest)491. 递增子序列动态规划失效上回溯由于需要找到所有的递增子序列动态规划就不行了妥妥用回溯套一个模板就出来了。回溯模板可参考仓库的 thinkings/backtrack.md 与 problems/90.subsets-ii.md。面试题 08.13. 堆箱子Hard别看它是 Hard掌握本文内容后一点都不难把箱子按三维尺寸排序然后求带权值的「三维严格递增子序列」权值是箱子的高度class Solution: def pileBox(self, box: List[List[int]]) - int: box sorted(box, keysorted) n len(box) dp [0 if i 0 else box[i - 1][2] for i in range(n 1)] ans max(dp) for i in range(1, n 1): for j in range(i 1, n 1): if box[j - 1][0] box[i - 1][0] and box[j - 1][1] box[i - 1][1] and box[j - 1][2] box[i - 1][2]: dp[j] max(dp[j], dp[i] box[j - 1][2]) ans max(ans , dp[j]) return ans354. 俄罗斯套娃信封问题Hard先按宽度或长度排序再对另一维求 LIS 即可class Solution: def maxEnvelopes(self, envelopes: List[List[int]]) - int: if not envelopes: return 0 n len(envelopes) dp [1] * n envelopes.sort() for i in range(n): for j in range(i 1, n): if envelopes[i][0] envelopes[j][0] and envelopes[i][1] envelopes[j][1]: dp[j] max(dp[j], dp[i] 1) return max(dp)小任务请尝试用贪心 二分在O(N log N)时间内完成本题参考上文优化小节即可。960. 删列造序 III按列做 LIS保留尽量多的「列」使这些列逐行非递减删除的列数就是总列数减去能保留的最大列数class Solution: def minDeletionSize(self, A): keep 1 m, n len(A), len(A[0]) dp [1] * n for j in range(n): for k in range(j 1, n): if all([A[i][k] A[i][j] for i in range(m)]): dp[k] max(dp[k], dp[j] 1) keep max(keep, dp[k]) return n - keep5644 / 1713. 得到子序列的最少操作次数由于这道题数据范围是10⁵因此只能使用O(N log N)的贪心才行。思路给target的元素建立「值 → 下标」的反向索引把arr中出现在target里的元素映射为下标序列B那么「target已是arr子序列的最长部分」就是B的 LIS 长度最少操作次数 len(target) - LIS(B)。仓库 problems/1713.minimum-operations-to-make-a-subsequence.md 中有完整的过程讲解class Solution: def minOperations(self, target: List[int], A: List[int]) - int: def LIS(A): d [] for a in A: i bisect.bisect_left(d, a) if d and i len(d): d[i] a else: d.append(a) return len(d) B [] target { t:i for i, t in enumerate(target)} for a in A: if a in target: B.append(target[a]) return len(target) - LIS(B)1626. 无矛盾的最佳球队不就是先按年龄、分数排下序然后求 scores 的最长上升不递减子序列并把「长度」换成「分数和」么class Solution: def bestTeamScore(self, scores: List[int], ages: List[int]) - int: n len(scores) persons list(zip(ages, scores)) persons.sort(keylambda x : (x[0], x[1])) dp [persons[i][1] for i in range(n)] for i in range(n): for j in range(i): if persons[i][1] persons[j][1]: dp[i] max(dp[i], dp[j]persons[i][1]) return max(dp)循环移位变体Circular LIS无非就是加了一个条件数组可循环。结合循环移位的技巧——把数组复制一份nums nums枚举每个起点求长度为n的窗口内的 LIS 并取最大值即可class Solution: def solve(self, nums): n len(nums) ans 1 def LIS(A): d [] for a in A: i bisect.bisect_left(d,a) if i len(d): d.append(a) else: d[i] a return len(d) nums nums for i in range(n): ans max(ans , LIS(nums[i:in])) return ans总结抽象思维是刷题的第一生产力把本文的思路搞懂、把这些题写一遍还怕碰到类似的题目不会么只有熟练掌握基础的数据结构与算法才能对复杂问题迎刃而解。最长上升子序列就是一个非常经典的基础算法把它彻底搞懂再去面对出题人的各种换皮就不怕了。反过来如果不去思考题目背后的逻辑就会刷得很痛苦——题目稍微一变化就不会了这也是很多人「刷了很多题碰到新题还是不会做」的原因之一。对照本文的六道主例题300 / 435 / 646 / 452 / 673 / 1713可以总结出 LIS 换皮题的三个关键抓手建模确认「子序列 求极值」的形态后优先定义dp[i]为「以i结尾的 xxx」转移时回头扫描所有j i排序区间、数对、信封、堆箱子类题目先按一维排序把二维/三维问题降维成一维 LIS改符号严格递增与不递减之间只差一个等号贪心 二分版本里则对应bisect_left与bisect_right的切换。与此主题配套仓库中的 selected/LCS.md 是它的姊妹篇最长公共子序列系列thinkings/dynamic-programming.md 则系统讲解了动态规划的状态定义与转移方程设计方法建议结合阅读把「套路识别」内化成自己的解题本能。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 穿上衣服我就不认识你了——最长上升子序列LIS套路全解【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读最长上升子序列Longest Increasing SubsequenceLIS是动态规划领域最经典的入门题型之一但出题人从不直接考它无重叠区间、最长数对链、引爆气球、堆箱子、俄罗斯套娃信封……这些看似八竿子打不着的题目本质上都是 LIS 的「换皮」。本文以仓库 selected/LIS.md 为主干逐题拆解 LIS 的动态规划建模过程再给出O(N log N)的贪心 二分优化并辅以仓库内 673. 最长递增子序列的个数、1713. 得到子序列的最少操作次数 等题解作为延伸证据帮你建立「透过现象看套路」的抽象思维读完本文你能识别并秒杀绝大多数 LIS 变种题。注意本文的目的是帮助你识别套路、从横向上理清解题思维框架并未采用最优解——文中给出的解法均可通过全部测试用例但并非每题的最优实现。想看更优解的读者可以自行查阅讨论区。300. 最长上升子序列LIS 本体题目描述给定一个无序的整数数组找到其中最长上升子序列的长度。示例输入:[10,9,2,5,3,7,101,18]输出:4解释: 最长的上升子序列是[2,3,7,101]它的长度是 4。说明可能会有多种最长上升子序列的组合你只需要输出对应的长度即可算法的时间复杂度应该为O(n²)进阶你能将算法的时间复杂度降低到O(n log n)吗思路两种状态定义选更可写的一种题目的意思是从给定数组中挑选若干数字这些数字满足「如果i j则nums[i] nums[j]」问一次最多可以挑选多少个满足条件的数字。这种「子序列求极值」的题目应当优先考虑贪心或动态规划。本题贪心不可行贪心无法回溯调整已做出的选择因此考虑动态规划。按照动态规划定义状态的套路有两种常见的定义方式dp[i]以i结尾一定包括i所能形成的最长上升子序列长度答案是max(dp[i])其中i 0, 1, 2, ..., n - 1dp[i]以i结尾可能包括i所能形成的最长上升子序列长度答案是dp[-1]-1 表示最后一个元素。第二种定义方式虽然无需比较不同的dp[i]就能直接获得答案看起来更方便但它的状态转移方程很不好写——因为dp[i]的末尾数字即最大的那个数可能是任意j i位置的元素无法唯一确定转移来源。这与仓库 thinkings/dynamic-programming.md 中讨论的状态定义困境一致状态定义一旦含糊转移方程就会难以确定。因此我们选择第一种建模方式。第一种方式虽然需要在循环时顺便比较不同的dp[i]来更新答案但对复杂度没有影响只是代码多几行而已。状态转移方程推导由于dp[j]中一定会包括j且以j结尾那么nums[j]一定是dp[j]所形成序列中的最大元素。若位于其后意味着i j的nums[i] nums[j]那么nums[i]一定能够融入dp[j]形成的序列从而构成一个更长的上升子序列其长度为dp[j] 1。于是状态转移方程为dp[i] max(dp[j] 1)其中 i j 且 nums[i] nums[j]以[10, 9, 2, 5, 3, 7, 101, 18]为例当计算到dp[5]对应元素 7时需要回头与位置 0、1、2、3、4 的元素逐一比较与dp[0]10比较7 10不成立跳过与dp[1]9比较7 9不成立跳过与dp[2]2比较7 2成立dp[5] max(1, dp[2] 1) 2与dp[3]5比较7 5成立dp[5] max(2, dp[3] 1) 3与dp[4]3比较7 3成立dp[5] max(3, dp[4] 1) 3。最后从所有候选中选出最大的一个加 1 赋给dp[5]即可。记住这个状态转移方程后面所有换皮题都会反复用到它。代码实现class Solution: def lengthOfLIS(self, nums: List[int]) - int: n len(nums) if n 0: return 0 dp [1] * n ans 1 for i in range(n): for j in range(i): if nums[i] nums[j]: dp[i] max(dp[i], dp[j] 1) ans max(ans, dp[i]) return ans复杂度分析时间复杂度O(N²)双层循环每对(i, j)比较一次空间复杂度O(N)一个长度n的dp数组。435. 无重叠区间删除变成「保留最长」题目描述给定一个区间的集合找到需要移除区间的最小数量使剩余区间互不重叠。注意可以认为区间的终点总是大于它的起点区间[1,2]和[2,3]的边界相互“接触”但没有相互重叠。示例 1输入[[1,2],[2,3],[3,4],[1,3]]输出1解释移除[1,3]后剩下的区间没有重叠。示例 2输入[[1,2],[1,2],[1,2]]输出2解释需要移除两个[1,2]来使剩下的区间没有重叠。示例 3输入[[1,2],[2,3]]输出0解释不需要移除任何区间因为它们已经无重叠。思路把区间看成「数字序列」先来看最终剩下的区间。由于剩下的区间互不重叠因此剩下的相邻区间的后一个区间的开始时间一定不小于前一个区间的结束时间。例如剩下的区间是[[1,2],[2,3],[3,4]]第一个区间的结束 2 小于等于第二个区间的开始 2第二个区间的结束 3 小于等于第三个区间的开始 3。不难发现如果把「前面区间的结束」和「后面区间的开始」结合起来看剩余区间序列就是一个非严格递增序列。而我们的目标正是删除若干区间从而剩下最长的非严格递增子序列。这不就是 300 题吗只不过 300 题要求严格递增这里允许相等——改一个符号变而已。反过来看300 题可以理解为「删除了若干数字剩下最长的严格递增子序列」。这就是抽象的力量这就是套路。由于要按序比较区间的「结束」与「开始」我们需要先对区间按起点或终点排序之后就转化为上面的最长递增子序列问题。与 300 题不同的是区间比较时拿后面的开始时间和前面的结束时间比较。还需要注意两点转化题目求的是需要移除的区间数量因此最后return时要做一个转化n - max(dp)题目不是要求严格递增而是可以相等因此判断条件要加上等号。这道题还有一种贪心解法效率优于动态规划但与本文主题不一致这里不再展开。代码实现你看代码多像class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) - int: n len(intervals) if n 0: return 0 dp [1] * n ans 1 intervals.sort(keylambda a: a[0]) for i in range(len(intervals)): for j in range(i - 1, -1, -1): if intervals[i][0] intervals[j][1]: dp[i] max(dp[i], dp[j] 1) break # 由于是按照开始时间排序的, 因此可以剪枝 return n - max(dp)复杂度分析时间复杂度O(N²)双层循环排序另计O(N log N)空间复杂度O(N)。646. 最长数对链去掉等号去掉转化题目描述给出n个数对。在每一个数对中第一个数字总是比第二个数字小。现在定义一种跟随关系当且仅当b c时数对(c, d)才可以跟在(a, b)后面。我们用这种形式来构造一个数对链。给定一个对数集合找出能够形成的最长数对链的长度。你不需要用到所有的数对可以以任何顺序选择其中的一些数对来构造。示例输入[[1,2],[2,3],[3,4]]输出2解释最长的数对链是[1,2] - [3,4]。注意给出数对的个数在[1, 1000]范围内。思路换皮只换了两处和上面的「435. 无重叠区间」是换皮题唯一的区别是这里又变成了严格递增b c。没关系我们把等号去掉改回就行了。并且这道题求解的是最长链的长度不是移除数量因此最后的n - max(dp)转化也不需要了直接返回max(dp)即可。当然这道题也有贪心解法效率优于动态规划与本文主题不一致这里不再展开。代码实现这代码更像了class Solution: def findLongestChain(self, intervals: List[List[int]]) - int: n len(intervals) if n 0: return 0 dp [1] * n ans 1 intervals.sort(keylambda a: a[0]) for i in range(len(intervals)): for j in range(i - 1, -1, -1): if intervals[i][0] intervals[j][1]: dp[i] max(dp[i], dp[j] 1) break # 由于是按照开始时间排序的, 因此可以剪枝 return max(dp)复杂度分析时间复杂度O(N²)空间复杂度O(N)。452. 用最少数量的箭引爆气球重叠也能算「不重叠」题目描述在二维空间中有许多球形的气球。对于每个气球输入是水平方向上气球直径的开始和结束坐标。由于它是水平的y 坐标并不重要只要知道开始和结束的 x 坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在 10⁴ 个气球。一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标x处射出一支箭若一个气球的直径开始和结束坐标为xstart, xend且满足xstart ≤ x ≤ xend则该气球会被引爆。可以射出的弓箭数量没有限制弓箭一旦射出可以无限前进。我们想找到使得所有气球全部被引爆所需弓箭的最小数量。示例输入[[10,16],[2,8],[1,6],[7,12]]输出2。解释可以在x 6射爆[2,8]、[1,6]两个气球在x 11射爆另外两个气球。思路重叠与「链」的等价把气球看成区间需要几支箭才能全部射爆意思就是这些区间能分成多少组互不相交不重叠的层——一支箭只能穿过互相重叠的气球。换句话说答案等价于「最多有多少个两两不重叠的区间」因为每组重叠的气球需要一支箭而不重叠的区间必然分属不同支箭。注意这里重叠的情况包括边界接触也能被同一支箭射爆即条件是xstart ≤ x ≤ xend。这么一抽象它就与上面的「646. 最长数对链」一模一样了——都是求「最多能选出多少个互不重叠或首尾衔接的区间」直接套用即可不用多说了吧这道题同样有更高效的贪心解法与本文主题不一致不再展开。代码实现代码像不像class Solution: def findMinArrowShots(self, intervals: List[List[int]]) - int: n len(intervals) if n 0: return 0 dp [1] * n ans 1 intervals.sort(keylambda a: a[0]) for i in range(len(intervals)): for j in range(i - 1, -1, -1): if intervals[i][0] intervals[j][1]: dp[i] max(dp[i], dp[j] 1) break # 由于是按照开始时间排序的, 因此可以剪枝 return max(dp)复杂度分析时间复杂度O(N²)空间复杂度O(N)。优化贪心 二分把 LIS 做到 O(N log N)上面的 DP 解法虽然思路清晰但O(N²)在处理10⁵量级的数据时会超时。LIS 也可以用贪心 二分达到O(N log N)的优良效率代码如下class Solution: def lengthOfLIS(self, A: List[int]) - int: d [] for a in A: i bisect.bisect_left(d, a) if i len(d): d[i] a elif not d or d[-1] a: d.append(a) return len(d)核心思想维护一个数组d其中d[k]表示「长度为k1的上升子序列的最小末尾值」。贪心在于末尾值越小越有利于后续元素接上去形成更长的序列。每来一个新元素a用二分bisect_left找到它在d中的插入位置若位置在数组内部则用a替换该位置的值因为a更小作为该长度的新末尾更优若位置超出数组末尾且a大于当前末尾则追加序列可以更长。最终len(d)就是 LIS 的长度。关于bisect_left/bisect_right的语义细节可参见仓库的二分专题 91/binary-search.md 与 thinkings/binary-search-2.md。变体最长不递减子序列如果求的是最长不递减子序列允许相等呢只需要把最左插入改为最右插入即可bisect_left改为bisect即bisect_right同时把追加条件的小于号改为小于等于号class Solution: def lengthOfLIS(self, A: List[int]) - int: d [] for a in A: # 这里改为最右 i bisect.bisect(d, a) if i len(d): d[i] a # 这里改为小于等号 elif not d or d[-1] a: d.append(a) return len(d)也可以写得更简洁一些def LIS(A): d [] for a in A: # 如果要求严格递增就改为最左插入 bisect_left 即可 i bisect.bisect(d, a) if i len(d): d.append(a) elif d[i] ! a: d[i] a return len(d)最左插入bisect_left与最右插入bisect_right分不清的读者可以看看仓库中的二分专题 thinkings/binary-search-2.md。More一网打尽 LIS 换皮题套路讲到这里剩下的就是「套模板」的环节了。以下题目在仓库中均有对应题解或可作为练习673. 最长递增子序列的个数滴滴面试题不就是先求出最长序列长度之后再循环比对一次就可以得出答案了么难点在于除了长度还要同步维护个数。仓库 problems/673.number-of-longest-increasing-subsequence.md 给出了完整推导用dp[i][0]表示以nums[i]结尾的 LIS 长度dp[i][1]表示该长度的子序列个数转移时「变长则继承个数、等长则累加个数」class Solution: def findNumberOfLIS(self, nums: List[int]) - int: n len(nums) # dp[i][0] - LIS # dp[i][1] - NumberOfLIS dp [[1, 1] for _ in range(n)] longest 1 for i in range(n): for j in range(i 1, n): if nums[j] nums[i]: if dp[i][0] 1 dp[j][0]: dp[j][0] dp[i][0] 1 # 下面这行代码容易忘记导致出错 dp[j][1] dp[i][1] longest max(longest, dp[j][0]) elif dp[i][0] 1 dp[j][0]: dp[j][1] dp[i][1] return sum(dp[i][1] for i in range(n) if dp[i][0] longest)491. 递增子序列动态规划失效上回溯由于需要找到所有的递增子序列动态规划就不行了妥妥用回溯套一个模板就出来了。回溯模板可参考仓库的 thinkings/backtrack.md 与 problems/90.subsets-ii.md。面试题 08.13. 堆箱子Hard别看它是 Hard掌握本文内容后一点都不难把箱子按三维尺寸排序然后求带权值的「三维严格递增子序列」权值是箱子的高度class Solution: def pileBox(self, box: List[List[int]]) - int: box sorted(box, keysorted) n len(box) dp [0 if i 0 else box[i - 1][2] for i in range(n 1)] ans max(dp) for i in range(1, n 1): for j in range(i 1, n 1): if box[j - 1][0] box[i - 1][0] and box[j - 1][1] box[i - 1][1] and box[j - 1][2] box[i - 1][2]: dp[j] max(dp[j], dp[i] box[j - 1][2]) ans max(ans , dp[j]) return ans354. 俄罗斯套娃信封问题Hard先按宽度或长度排序再对另一维求 LIS 即可class Solution: def maxEnvelopes(self, envelopes: List[List[int]]) - int: if not envelopes: return 0 n len(envelopes) dp [1] * n envelopes.sort() for i in range(n): for j in range(i 1, n): if envelopes[i][0] envelopes[j][0] and envelopes[i][1] envelopes[j][1]: dp[j] max(dp[j], dp[i] 1) return max(dp)小任务请尝试用贪心 二分在O(N log N)时间内完成本题参考上文优化小节即可。960. 删列造序 III按列做 LIS保留尽量多的「列」使这些列逐行非递减删除的列数就是总列数减去能保留的最大列数class Solution: def minDeletionSize(self, A): keep 1 m, n len(A), len(A[0]) dp [1] * n for j in range(n): for k in range(j 1, n): if all([A[i][k] A[i][j] for i in range(m)]): dp[k] max(dp[k], dp[j] 1) keep max(keep, dp[k]) return n - keep5644 / 1713. 得到子序列的最少操作次数由于这道题数据范围是10⁵因此只能使用O(N log N)的贪心才行。思路给target的元素建立「值 → 下标」的反向索引把arr中出现在target里的元素映射为下标序列B那么「target已是arr子序列的最长部分」就是B的 LIS 长度最少操作次数 len(target) - LIS(B)。仓库 problems/1713.minimum-operations-to-make-a-subsequence.md 中有完整的过程讲解class Solution: def minOperations(self, target: List[int], A: List[int]) - int: def LIS(A): d [] for a in A: i bisect.bisect_left(d, a) if d and i len(d): d[i] a else: d.append(a) return len(d) B [] target { t:i for i, t in enumerate(target)} for a in A: if a in target: B.append(target[a]) return len(target) - LIS(B)1626. 无矛盾的最佳球队不就是先按年龄、分数排下序然后求 scores 的最长上升不递减子序列并把「长度」换成「分数和」么class Solution: def bestTeamScore(self, scores: List[int], ages: List[int]) - int: n len(scores) persons list(zip(ages, scores)) persons.sort(keylambda x : (x[0], x[1])) dp [persons[i][1] for i in range(n)] for i in range(n): for j in range(i): if persons[i][1] persons[j][1]: dp[i] max(dp[i], dp[j]persons[i][1]) return max(dp)循环移位变体Circular LIS无非就是加了一个条件数组可循环。结合循环移位的技巧——把数组复制一份nums nums枚举每个起点求长度为n的窗口内的 LIS 并取最大值即可class Solution: def solve(self, nums): n len(nums) ans 1 def LIS(A): d [] for a in A: i bisect.bisect_left(d,a) if i len(d): d.append(a) else: d[i] a return len(d) nums nums for i in range(n): ans max(ans , LIS(nums[i:in])) return ans总结抽象思维是刷题的第一生产力把本文的思路搞懂、把这些题写一遍还怕碰到类似的题目不会么只有熟练掌握基础的数据结构与算法才能对复杂问题迎刃而解。最长上升子序列就是一个非常经典的基础算法把它彻底搞懂再去面对出题人的各种换皮就不怕了。反过来如果不去思考题目背后的逻辑就会刷得很痛苦——题目稍微一变化就不会了这也是很多人「刷了很多题碰到新题还是不会做」的原因之一。对照本文的六道主例题300 / 435 / 646 / 452 / 673 / 1713可以总结出 LIS 换皮题的三个关键抓手建模确认「子序列 求极值」的形态后优先定义dp[i]为「以i结尾的 xxx」转移时回头扫描所有j i排序区间、数对、信封、堆箱子类题目先按一维排序把二维/三维问题降维成一维 LIS改符号严格递增与不递减之间只差一个等号贪心 二分版本里则对应bisect_left与bisect_right的切换。与此主题配套仓库中的 selected/LCS.md 是它的姊妹篇最长公共子序列系列thinkings/dynamic-programming.md 则系统讲解了动态规划的状态定义与转移方程设计方法建议结合阅读把「套路识别」内化成自己的解题本能。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考