题目给你一个整数数组 nums 找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。子序列 是可以通过从另一个数组删除或不删除某些元素但不更改其余元素的顺序得到的数组。示例 1输入nums [10,9,2,5,3,7,101,18]输出4解释最长递增子序列是 [2,3,7,101]因此长度为 4 。示例 2输入nums [0,1,0,3,2,3]输出4示例 3输入nums [7,7,7,7,7,7,7]输出1提示1 nums.length 2500-104 nums[i] 104思路这个题目还是使用动态规划解决首先确定题目所求最长子序列定义元素全部来自原数组元素在原数组中的「出现顺序不变」判断一个序列是否为子序列必须看「原数组索引是否严格递增」—— 只要索引出现 “后一个比前一个小”就不是子序列。动态规划首先定义dp[i]代表nums 中以 nums[i] 结尾的最长子序列长度其次确定转移方程0ji当前num[i] num[j] 时dp[i]max(dp[i],dp[j]1)for j in [0, i)就是类似于在当前 [0, i) 的范围内遍历 [0, i) 找到 nums数组中 从 [0, i) 中所有小于 nums[i] 的元素再通过当前 元素 num[j] 的最长子序列长度 1更新最大值之后定义边界条件每一个num[i]的初始化都为1因为元素本身也是一个子序列最后选择策略自底向上时间复杂度 O(N ^2 ) 遍历计算 dp 列表需 O(N)计算每个 dp[i] 需 O(N)。空间复杂度 O(N) dp 列表占用线性大小额外空间。动态规划 二分查找传统方法是每个num[i]都和之前 [0, i) 中所有元素都比一遍效率低这个解法的思路是始终让当前的所求最长子序列记为候选队列的最后一个元素值最小以此达到 所求最长子序列 每次可以拼接的值更多达到最优因此最终所求最长子序列长度为候选序列的长度想要让递增子序列尽可能长那对于同样长度的递增子序列来说它的末尾元素越小后面就越容易接上更大的数字也就越有潜力变得更长。举个直观例子长度为 3 的子序列 A[2, 5, 7]末尾是 7长度为 3 的子序列 B[2, 3, 6]末尾是 6显然 B 更 “优秀”—— 后面如果来个数字 8两个都能接但如果来个数字 7B 能接6 7A 就接不了7 不小于 7。维护一个数组叫「候选序列」比如叫 tails它的含义是tails[i] 表示 所有长度为 i1 的递增子序列中末尾元素的最小值举例如果有两个长度为 2 的递增子序列 [2,5] 和 [2,3]那么 tails[1]因为 i12i1会选 3因为 3 比 5 小后面如果来个 4能接在 3 后面形成 [2,3,4]长度 3但接在 5 后面就不行核心作用是为后续元素提供 “最小的尾部”留足空间搭更长的序列。关键逻辑如下建 “候选库”初始化一个空数组 tails负责存 “不同长度子序列的最小尾部”逐个处理元素x nums[i]x 比 tail 末尾的元素还大 → 直接加入可以把 x 接在当前最长的子序列后面得到一个更长的递增子序列。x 小于等于 tail 末尾的元素说明 x 无法延长当前最长子序列但它可以优化某个长度的最小末尾值。操作在 tail 数组中找到第一个大于等于 x 的元素用 x 替换掉它。用二分找 “候选库” 里第一个比它大的元素把那个元素换成它优化 “候选库”给后面元素留空间意义替换后对应长度的子序列末尾变得更小了后续更容易被延长同时已经得到的最长长度不会受到任何影响看 “候选库” 长度遍历结束后tails 有多长最长递增子序列就有多长。替换操作会不会破坏已经得到的最大长度绝对不会。替换只发生在已有长度的范围内只会让对应长度的末尾更小不会让 tailLen 变小而 tailLen 一旦增长就不会回落最终结果一定是正确的最大长度。为什么 right 初始是 tailLen而不是 tailLen-1因为采用的是左闭右开区间写法[0, tailLen)刚好覆盖所有有效元素同时如果 x 比所有元素都大最终 left 会等于 tailLen刚好对应 “追加到末尾” 的位置无需额外判断。为什么找 “第一个大于等于”而不是大于因为题目要求的是严格递增子序列相等的元素不能算递增所以遇到相等值时也要替换保证 tail 严格递增。如果题目允许非递减就改成找第一个大于的位置即可。算法动态规划classSolution{publicintlengthOfLIS(int[]nums){intlennums.length;if(len0)return0;int[]dpnewint[len];Arrays.fill(dp,1);intres0;for(inti0;ilen;i){for(intj0;ji;j){if(nums[i]nums[j]){dp[i]Math.max(dp[i],dp[j]1);}}resMath.max(res,dp[i]);}returnres;}}动态规划 二分查找classSolution{publicintlengthOfLIS(int[]nums){int[]tailnewint[nums.length];inttailLen0;for(inti0;inums.length;i){intleft0,righttailLen;while(leftright){// 二分查找在tails[0..len-1]里找第一个比num大的位置intmid(leftright)/2;if(tail[mid]nums[i]){// 要找比num大的所以mid处小的话左边界右移leftmid1;}else{rightmid;}}// 循环结束后left就是要替换的位置tail[left]nums[i];// 如果替换的是最后一个位置left len说明候选序列变长了if(tailLenleft)tailLen;}returntailLen;}}