LeetCode 300. 最长递增子序列 题目描述题目级别中等给你一个整数数组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。 解法一动态规划 (回头找垫脚石)面对子序列问题动态规划是最正统的解法。状态定义定义dp[i]表示以nums[i]这个数结尾的最长递增子序列的长度。(注意这里必须是以它结尾这样我们才能确切知道下一个数能不能接在它后面。)状态转移方程假设我们正在考察第i个数字我们如何求它的dp[i]我们只需要回头看它前面的所有数字假设索引为j0 j i只要nums[i] nums[j]说明nums[i]可以完美地接在nums[j]的后面形成一个更长的递增子序列。所以我们在所有符合条件的j中挑一个dp[j]最大的接上去再加上自己本身的长度 1 即可dp[i] max(dp[i], dp[j] 1)初始化每个数字自己本身就可以构成一个长度为 1 的子序列所以dp数组初始全部赋值为1。 C 代码实现 (DP 法)classSolution{public:intlengthOfLIS(vectorintnums){intnnums.size();if(n0)return0;// 规范写法使用 vector 开辟状态数组并全部初始化为 1vectorintdp(n,1);intres1;for(inti0;in;i){// 内层循环回头寻找可以接上去的“垫脚石”for(intj0;ji;j){if(nums[i]nums[j]){dp[i]max(dp[i],dp[j]1);}}// 记录整个过程中出现的最大长度resmax(res,dp[i]);}returnres;}};进阶挑战你能将算法的时间复杂度降低到O(nlog⁡n)O(n \log n)O(nlogn)吗? 解法二贪心策略 二分查找为了让递增子序列尽可能的“长”我们需要秉持一个贪心的原则让子序列的增长速度尽可能的慢换句话说每次加进来的数字越小后面能接上的数字就越多。我们可以维护一个名为tails的数组tails[k]表示长度为k1的递增子序列中末尾最小的那个数字。核心运作机制遍历原数组nums对于当前数字num如果num比tails数组的最后一个元素还要大简直完美说明它可以直接接在当前最长的子序列后面让最大长度加 1。我们直接把它push_back到tails末尾。如果num没有比最后一个元素大它虽然不能增加最长子序列的长度但它是一个“潜力股”。我们要在tails数组中找到第一个大于等于num的元素并用num去替换它为什么因为tails数组天然是严格递增的把较大的末尾元素换成较小的num不会改变当前子序列的长度但会让末尾数字变小为后续接上更多的数字创造了有利条件。由于tails数组是严格递增的在其中寻找“第一个大于等于num的元素”这一步我们可以直接使用二分查找将这部分的时间从O(N)O(N)O(N)降到O(log⁡N)O(\log N)O(logN)。 C 代码实现 (贪心二分法)classSolution{public:intlengthOfLIS(vectorintnums){// tails 数组存储当前各个长度的递增子序列的最小末尾元素vectorinttails;for(intnum:nums){// 如果 tails 为空或者当前数字大于 tails 的最后一个数字直接追加if(tails.empty()||numtails.back()){tails.push_back(num);}else{// 否则使用二分查找找到 tails 中第一个 num 的元素intl0,rtails.size()-1;while(lr){intmidl(r-l)/2;if(tails[mid]num){rmid;// 目标在左侧或就是 mid}else{lmid1;// 目标在右侧}}// 用更小的 num 替换掉原来的较大元素培养潜力tails[l]num;// 也可以一行代码搞定// *lower_bound(tails.begin(), tails.end(), num) num;}}// tails 数组的最终长度就是最长递增子序列的长度returntails.size();}};