[LeetCode] 300、最长上升子序列

题目描述给定一个无序的整数数组找到其中最长上升子序列的长度。示例输入:[10,9,2,5,3,7,101,18]输出:4解释:最长的上升子序列是[2,3,7,101]它的长度是4。说明:可能会有多种最长上升子序列的组合你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2) 。进阶: 你能将算法的时间复杂度降低到O ( n l o g n ) O(n log n)O(nlogn)吗?解题思路这是一个子序列问题子序列问题基本都可以归化为“动态规划”问题。动态规划四要素状态表示、初始化、状态转移方程、返回值使用数组cell保存每步子问题的最优解cell[i]代表以nums[i]为结尾的最长上升子序列长度求解cell[i]时向前遍历找出比i元素小的元素j状态转移方程为cell[i] maxcell[i], cell[j] 1)。0 j i cell[j] cell[i]初始化cell[0] 1一定要把整个数组全部初始化为1迭代过程中不断更新最大值返回值为迭代过程中的最大值。两次遍历数组时间复杂度O ( n 2 ) O(n^2)O(n2)。动态规划 二分进阶要求时间复杂度要求O ( n l o g n ) O(nlogn)O(nlogn)立马想到二分。这个思路比较巧妙很具小巧思。新建数组cell用于保存最长上升子序列保存的是序列不是状态表示了。对原序列进行遍历将每位元素二分插入cell中。如果cell中元素都比它小将它插到最后。否则用它覆盖掉大于等于它的元素中最小的那个。总之思想就是让cell中存储比较小的元素。这样cell未必是真实的最长上升子序列但长度是对的。参考代码动态规划也要会classSolution{public:intlengthOfLIS(vectorintnums){intlengthnums.size();if(length1){return1;}intres1;// 结果默认值为1vectorintdp(length,1);for(inti1;ilength;i){for(intj0;ji;j){if(nums[j]nums[i]){dp[i]max(dp[i],dp[j]1);}}resmax(res,dp[i]);}returnres;}};按照模板写的二分推荐核心思想维护一个数组 res始终保持严格递增且 res 的长度就是当前最长上升子序列的长度。关键点res 不一定是真实的最长子序列但它的长度一定是对的。为什么替换不会破坏长度的正确性替换操作只是把 res[idx] 换成更小的值既没有让 res 变长长度不变也没有让 res 变短长度不变只是让 res[idx] 变得更小为后续元素创造更大的上升空间一句话总结res 中的元素不一定是真实子序列但通过贪心地用更小的值替换保证了 res 始终是最优状态使得后续元素有最大的上升空间因此 res.size() 始终等于当前最长上升子序列的长度。classSolution{public:intlengthOfLIS(vectorintnums){intleft0,rightnums.size()-1;vectorintres;for(inti0;inums.size();i){if(res.empty()||nums[i]res.back()){res.push_back(nums[i]);continue;}intidxbinarySearchIdx(res,nums[i]);// 注意这里传的数组是resres[idx]nums[i];}returnres.size();}// 首先要明确我们的目的是要找第一个“大于等于k”的元素的下标intbinarySearchIdx(vectorintnums,inttarget){intleft0,rightnums.size()-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){leftmid1;}else{rightmid;}}returnleft;}};进阶要求返回最长的上升子序列核心思路在 DP 的同时用一个 path 数组记录每个位置的最优前驱节点最后从终点往前回溯。参考代码基于上述dp的方法改动几点而已classSolution{public:vectorintlengthOfLIS(vectorintnums){intlengthnums.size();if(length1){return{nums[0]};}intres1;intendPos0;// 新增记录最长子序列的结束位置vectorintdp(length,1);// dp[i] 表示以 nums[i] 结尾的最长上升子序列长度vectorintpath(length,-1);// 新增path[i] 记录每个位置 i 的前驱节点索引默认-1for(inti1;ilength;i){for(intj0;ji;j){if(nums[j]nums[i]){if(dp[j]1dp[i]){// 原来的 max 改成 if方便同时更新 pathdp[i]dp[j]1;path[i]j;// 新增更新前驱}}}if(dp[i]res){resdp[i];endPosi;// 新增更新结束位置}}// 新增从 endPos 沿 path 回溯还原子序列vectorintresult;for(intiendPos;i!-1;ipath[i]){// 注意这里的 i path[i] 操作很骚result.push_back(nums[i]);}reverse(result.begin(),result.end());returnresult;}};