力扣300-最长递增子序列

题目链接300. 最长递增子序列 - 力扣LeetCode给你一个整数数组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进阶你能将算法的时间复杂度降低到O(n log(n))吗?方法一动态规划从一般情况考虑求dp[i]设dp[i]表示以nums[i]结尾的最长递增子序列长度只需要找出nums[i]之前比其小的nums[j]那么dp[i]就等于dp[j] 1由于要求最大所以在遍历的时候用max更新最大的即可递推公式已经出来了接着考虑初始化。显然每个元素都初始化为1因为一个数字也可以构成一个子序列最后用max更新最大的dp[i]即可Javaclass Solution { public int lengthOfLIS(int[] nums) { int n nums.length; int[] dp new int[n]; Arrays.fill(dp, 1); int ans dp[0]; for(int i 1; i n; i) { for(int j i - 1; j 0; j--) { if(nums[i] nums[j]) { dp[i] Math.max(dp[i], dp[j] 1); } } ans Math.max(ans, dp[i]); } return ans; } }Cclass Solution { public: int lengthOfLIS(vectorint nums) { int ans0; int nnums.size(); if (n1) return n; vectorintdp(n,1); for(int i1;in;i) { for(int j0;ji;j) { if(nums[j]nums[i]) { dp[i]max(dp[i],dp[j]1);//这里不是比较而是更新最大值 } } ansmax(ans,dp[i]);//这里同理也是在更新最大值 } return ans; } };Gofunc lengthOfLIS(nums []int) int { dp:make([]int,len(nums)) for i: range dp { dp[i]1 } ans:dp[0] for i:1;ilen(nums);i { for j:0;ji;j { if nums[j]nums[i] { dp[i]max(dp[i],dp[j]1) } } ansmax(ans,dp[i]) } return ans }时间复杂度为O(N^2)考虑进行优化方法二贪心二分假设nums为[1,2,99999,3,4]当遍历完前两个元素也就是1和2之后此时最长递增子数组以下简称LIS为[1,2]接下来你会选择99999加入LIS中还是选择后面的3加入到LIS中显然应该选择更小的3如果选择99999那么就会错过3后面的4选择了3就能得到正确的LIS即[1,2,3,4]这是一种贪心思想为了使数组递增的长度更大我们应该让它增长的速度尽可能慢这样就尽可能避免了错过后面单增的可能表示一种“最可能性”落实到具体数组中我们的选择策略尽管依然是选择比LIS中元素更大的元素但是新增了一个条件是要在这些更大的元素中选择最小的那个。但问题来了我们在遍历的时候怎么知道后面的元素是否有更小的我们可以记录当前LIS的长度len用一个数组d记录LIS的末尾元素也就是最大值的最小值即d[len]表示长度为len的LIS的末尾元素的最小值显然d[i]随i的增大而增大。因为如果d[j]≥d[i]且 ji考虑从长度为i的最长上升子序列的末尾删除 i−j 个元素那么这个序列长度变为 j 且第 j 个元素 x末尾元素必然小于d[i]因为第j个元素不是最后一个元素就必然比最后一个元素要小也就小于d[j]那么就找到了一个长度为 j 的最长上升子序列并且末尾元素比d[j]小而d[j]的定义是长度为j的LIS的末尾元素的最小值这与定义相矛盾因此单调性得证如果遍历的元素nums[i]比d[len]更小说明存在一种“增长速度更慢”的可能是哪个子数组的增长速度可能更慢为了回答这个问题我们需要在d中找到从右往左数第一个比nums[i]更小的元素由于d有序可以用二分。假设其位置为k那么将d[k1]替换为nums[i]后d[1...k1]的增长速度就比没替换之前更慢长度为k1的LIS后续变得更长的可能性就变高了如果nums[i]比d[len]更大那就意味着nums[i]可以成为长度为len1的LIS的末尾元素。直接让len自增1并且让d[len1]为nums[i]即可因为此时len的长度发生了变化只有一个长度为len1的LIS所以末尾元素的最小值只能是新加入的nums[i]了Javaclass Solution { public int lengthOfLIS(int[] nums) { int n nums.length; if(n 0) return 0; int[] d new int[n 1]; //d[len]表示长度为len的LIS末尾元素的最小值 int len 1; //LIS的长度初始时只有第一个元素因此为1 d[len] nums[0]; //初始时len为1LIS为第一个元素自己构成的数组所以最小值就是它本身 for(int i 1; i n; i) { if(nums[i] d[len]) { //长度为len的、末尾元素最小的LIS的最大值遇到了比它更大的元素应该将其加入该LIS当中 d[len] nums[i]; //原本长度为len现在长度为len1d[len1]表示的是长度为len1的LIS末尾元素的最小值 } else { //二分法找到d中从右往左数第一个比nums[i]小的位置pos让d[pos1]为nums[i] //如果d中所有元素都比nums[i]要大更新d[1]因为以nums[i]结尾的、长度为1的LIS有最小的末尾元素所以pos初始值为0 int pos 0; int l 1, r len; //d[0]没有实际含义所以左端点为1右端点为len while(l r) { int mid (l r) 1; if(d[mid] nums[i]) { pos mid; l mid 1; } else { r mid - 1; } } d[pos 1] nums[i]; } } return len; } }