LeetCode 300最长递增子序列1. 题目核心给定整数数组nums求其中最长严格递增子序列的长度。子序列不要求连续但必须保持原数组中的相对顺序。例如nums [10,9,2,5,3,7,101,18]一种最长递增子序列2 → 3 → 7 → 101长度为4注意子数组必须连续 子序列可以跳过中间元素2. 思路一DFS / 枚举对于每个数字都可以考虑选择它 不选择它然后枚举所有可能的子序列判断是否严格递增并记录最大长度。这种方法会产生大量重复情况最坏接近指数级复杂度不适合作为主解。3. 思路二动态规划 DP3.1 DP 状态定义这题最关键的是不能只记录“当前最长的那一条序列”因为当前数字可能接不上最长序列却可以接在另一条较短但结尾更小的序列后面并在以后反超。因此定义dp[i] 以 nums[i] 作为最后一个数字时 最长递增子序列的长度例如nums [1,5,2,3,4]可能得到nums1 5 2 3 4 dp 1 2 2 3 4其中dp[1] 2 → 1,5 dp[2] 2 → 1,2虽然两者长度相同但是1,2的结尾更小所以后面可以继续接1 → 2 → 3 → 4最终超过原来的1 → 5。3.2 状态转移现在处理nums[i]检查它前面的所有位置j 0 ~ i-1如果nums[j] nums[i]说明nums[i]可以接在以nums[j]结尾的递增子序列之后。原来的长度dp[j]加上当前数字dp[j] 1因为可能有多个j都满足条件所以选择最大的dp[i] max(dp[i], dp[j] 1);完整关系对于所有 j i 如果 nums[j] nums[i] dp[i] max(dp[i], dp[j] 1)3.3 为什么初始化全部为 1任何一个数字单独拿出来都能形成长度为1的递增子序列vectorint dp(n, 1);例如[7]本身就是长度为1的递增子序列。3.4 为什么不能只和前一个数字比较错误思路if (nums[i] nums[i - 1]) dp[i] dp[i - 1] 1; else dp[i] 1;这算的是连续递增子数组不是递增子序列。例如nums [0,1,0,3,2,3]最长递增子序列0 → 1 → 2 → 3长度为4。其中2并不比它前面的3大3 2但它可以跳过3接在0 → 1后面。3.5 示例完整推导nums [0,1,0,3,2,3]初始化dp [1,1,1,1,1,1]处理10 1 dp[1] dp[0] 1 2 dp [1,2,1,1,1,1]处理第二个0前面没有比0小的数字 dp[2] 1 dp [1,2,1,1,1,1]处理30 3 → 112 1 3 → 213 0 3 → 112 dp[3] 3 dp [1,2,1,3,1,1]处理20 2 → 2 1 2 → 3 0 2 → 2 3 2 → 不能接 dp[4] 3 dp [1,2,1,3,3,1]最后处理32 3 dp[4] 1 4得到dp [1,2,1,3,3,4]答案43.6 为什么最终不能直接返回dp[n-1]因为dp[i]表示的是必须以nums[i]结尾的最长递增子序列。整个数组的最长递增子序列不一定以最后一个数字结束。例如nums [1,2,3,0] dp [1,2,3,1]答案应该是3而不是dp[3] 1所以需要maxLen max(maxLen, dp[i]);4. CDP 解法class Solution { public: int lengthOfLIS(vectorint nums) { int n nums.size(); // dp[i]以 nums[i] 结尾的最长递增子序列长度 vectorint dp(n, 1); int maxLen 1; for (int i 1; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] max(dp[i], dp[j] 1); } } maxLen max(maxLen, dp[i]); } return maxLen; } };复杂度时间复杂度O(n²) 空间复杂度O(n)5. 最优思路贪心 二分查找DP 的问题是每个nums[i]都要检查前面的所有数字所以需要O(n²)。可以维护一个数组tails其中tails[len-1] 长度为 len 的递增子序列中 能够得到的最小结尾值例如处理nums [10,9,2,5,3,7,101,18]过程大致为10 → [10] 9 → [9] 2 → [2] 5 → [2,5] 3 → [2,3] 7 → [2,3,7] 101 → [2,3,7,101] 18 → [2,3,7,18]最终tails.size() 4所以最长递增子序列长度为4。注意tails不一定是真实的最长递增子序列它主要用来记录“同样长度下尽可能小的结尾”。5.1 为什么结尾越小越好例如已经有1 → 5又遇到2虽然1 → 2长度仍然是2但结尾从5变成2。显然以2结尾比以5结尾更容易继续接3、4等数字。所以我们始终希望同样长度的递增子序列结尾越小越好。5.2 每个数字怎么处理对于当前数字x如果x比tails所有数字都大说明可以延长最长递增子序列直接放到末尾否则找到tails中第一个大于等于x的位置用x替换它。例如tails [2,5] 当前 x 3找到第一个 3的是5替换[2,5] ↓ [2,3]长度没变但结尾变小了为后面留下更多可能。5.3 为什么找“第一个 x”题目要求的是严格递增。如果tails [2,3,7] x 3不能把另一个3接到后面形成2 → 3 → 3因为不是严格递增。所以要找到第一个 x的位置进行替换。C 正好可以使用lower_bound()6. C最优解 O(n log n)class Solution { public: int lengthOfLIS(vectorint nums) { vectorint tails; for (int x : nums) { auto it lower_bound(tails.begin(), tails.end(), x); if (it tails.end()) { tails.push_back(x); } else { *it x; } } return tails.size(); } };复杂度时间复杂度O(n log n) 空间复杂度O(n)7. Java最优解class Solution { public int lengthOfLIS(int[] nums) { int[] tails new int[nums.length]; int size 0; for (int x : nums) { int left 0; int right size; while (left right) { int mid left (right - left) / 2; if (tails[mid] x) { left mid 1; } else { right mid; } } tails[left] x; if (left size) { size; } } return size; } }8. Java 语法解释8.1 创建数组int[] tails new int[nums.length];创建一个和nums一样长的整数数组。8.2 增强 for 循环for (int x : nums)表示依次取出数组中的每个数字对应 Cfor (int x : nums)8.3 二分查找范围int left 0; int right size;查找范围是[0, size)寻找第一个tails[index] x的位置。8.4 二分判断if (tails[mid] x) { left mid 1; } else { right mid; }如果tails[mid] x说明当前位置太小答案一定在右边。否则当前mid有可能就是第一个 x的位置因此right mid;8.5left size如果二分结束left size说明整个tails中都没有 x的数字也就是x 比所有结尾都大可以延长最长递增子序列size;9. Python最优解from bisect import bisect_leftclass Solution: def lengthOfLIS(self, nums): tails [] for x in nums: index bisect_left(tails, x) if index len(tails): tails.append(x) else: tails[index] x return len(tails)10. Python 语法解释10.1bisect_leftfrom bisect import bisect_left导入 Python 自带的二分查找函数。index bisect_left(tails, x)表示在已经有序的tails中寻找第一个 x的位置。基本对应 Clower_bound(tails.begin(), tails.end(), x)10.2 空列表tails []创建一个空列表。10.3appendtails.append(x)把x添加到列表末尾对应 Ctails.push_back(x);10.4lenlen(tails)表示列表长度。11. 两种主要解法对比方法时间复杂度空间复杂度特点DFS / 枚举指数级较高不推荐动态规划O(n²)O(n)最容易理解重点掌握贪心 二分O(n log n)O(n)最优常规解法12. 核心记忆12.1 DP 定义dp[i] 以 nums[i] 结尾的 最长递增子序列长度12.2 DP 转移对于所有j i如果nums[j] nums[i]则dp[i] max(dp[i], dp[j] 1);本质是当前数字去前面寻找所有比自己小的数字从它们对应的递增子序列中选择最长的一条再把自己接上去。12.3 为什么不能只保存一条最长序列例如1 → 5 1 → 2虽然长度都是2但第二条结尾更小未来更容易继续1 → 2 → 3 → 4所以 DP 要给每个位置分别保存一个状态不能只记录一个全局最长序列。12.4 最优解核心维护tails[len-1] 长度为 len 的递增子序列中 最小的结尾值当前数字x比所有结尾都大 → 添加到 tails 末尾 否则 → 找第一个 x 的位置并替换最后tails 的长度 LIS 长度一句话记忆DP 是“当前数字去前面找所有能接的序列”二分优化则是“只保留每种长度下最小的结尾”因为结尾越小未来越容易继续增长。