「这是我参与11月更文挑战的第8天，活动详情查看：2021最后一次更文挑战」
给你一个整数数组 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(n2)的解决方案吗？ - 你能将算法的时间复杂度降低到
O(n log(n))吗?
本题是是求最长递增子序列，那么涉及到这种求最优解的题，一般首先想到的解题方法就是动态规划
说到动态规划，就要说一下两个概念
状态定义
所谓状态定义，就是用一个函数符号 f(x) 以及该函数符号对应的含义描述，该函数符号对应的值就是要求解的值
如果没有接触过动态规划的小伙伴，看完上面这句话，可能你还是不太明白状态定义到底是什么，接下来我们就用本题举例，来看下本题如何做状态定义
首先我们思考一个问题：本题最长递增子序列的值和什么有关系？
答：本题最长子序列的值只和当前下标位置又关
我们想一下，如果我们当前在下标 0 的位置，最长递增子序列的长度就是 1，以此类推，随着下标位置的变化，最长递增子序列的长度也会发生变化
所以本题我们定义 dp[i] 表示下标 i 位置的最长递增子序列的长度
接下来我们看一下什么是状态转移方程
状态转移方程
状态定义完成后，我们并不能解决本题，我们知道 dp[i] 代表 下标 i 位置的最长递增子序列的长度，可是 0 下标位置的值很简单就是 1,但是 dp[nums.length-1] 的值是多少怎么得到呢？
这就是状态转移方程要做的事
我们想一下最长递增子序列满足的条件是什么？
是后面的元素要比前面的元素大，这就要求两个条件，假设后面的元素下标为 i,前面的元素下标为 j,则需要满足 j < i && nums[j] < nums[i],由此，我们就可以推断出本题的状态转移方程
dp[i] = dp[j]+1 //其中 j < i && nums[j] < nums[i]
所以我们只需要在 i 之前找到所有满足条件的 j 位置，让 dp[i] 等于所有满足条件的 dp[j] 中的最大值 +1即可
以上就是动态规划解题的两个步骤，也就形成了本题题解1的解题思路
题解1
var lengthOfLIS = function(nums) { const len = nums.length, dp = Array(len).fill(1); for(let i = 1;i<len;i++){ for(let j = 0;j<i;j++){ if(nums[j]<nums[i]) dp[i] = Math.max(dp[i],dp[j]+1) } } return Math.max(...dp) }; 复制代码
提交通过，用时 190ms 左右，在用时方面，只击败了 50% 左右的用户，时间复杂度是 O(n²) 的
题解2
上面题解的效率，作为一个有追求的前端，我肯定是不满意的，所以我用了一个下午的碎片化时间来思考有没有更优的解法，最终在第二天上午我放弃了
现阶段水平有限，没有想到更优的解法，动态规划也是刚开始学，于是我只能不甘心的去看一看大佬的题解 参考题解
这里说一下，通常我不会先看讲解的过程，而是直接拿到代码，运行没有问题，然后自己去理解代码
我感觉这样的话，有一个自己理解的过程，印象会更深一些，而且因为是自己理解的东西，过一段时间再回头看，也能很容易的回想起来
当然，如果理解的过程中遇到问题或者有了自己的理解，还是会去看一下讲解，前者解决问题，后者对比下自己的理解是否正确
所以接下来我的讲解过程会和原题解不太一样，感兴趣的小伙伴可以去看下原题解，顺便帮大佬点个赞，留个言，吃水不忘挖井人嘛！
我们来看一下示例1中给出的 nums = [10,9,2,5,3,7,101,18]
我们在该数组中想找到一个最长的递增子序列，如果把元素值的大小转换为高度，以上数组则如下图
在示例2给出的 nums = [0,1,0,3,2,3]如下图：
那我们想要求得的最长递增子序列，就是找到一个最长的连续上升的阶梯，那从这样的图中找出最长递增子序列，就是要把那些违反该性质的柱子，也就是元素，干掉。
那这个过程怎么做呢？
我们可以遍历所有的柱子，当前面的柱子大于它的时候，它就替换前面的柱子，如果前面没有大于它的柱子，就放在前面柱子的后面，而为了保证我们找到的上升阶梯最长，所以我们优先替换左侧的柱子
示例1的过程如下：
10 9 2 2 5 2 3 2 3 7 2 3 7 101 2 3 7 101 18 复制代码
示例2的过程如下：
0 0 1 0 1 0 1 3 0 1 2 0 1 2 3 复制代码
最后，柱子的个数，就是最长递增子序列的长度
那这个过程为什么可以合理的求得最长上升子序列呢？
因为我们遍历元素的过程是从左向右的，也就是从下标 0 到数组末尾，所以在一次柱子从低到高排列的过程中，下标肯定是有序的
又因为我们把高的柱子放在矮的柱子后面，所以柱子的高低，也就是元素值的大小也是有序的
可能最后我们最终的柱子不是对应原数组的一组阶梯柱子，那是因为后续更新的柱子没有完整覆盖上一组柱子
我知道这里如果用动画演示会更好一些，但因为现阶段水平有限，所以没有搞动图，但是我们可以用元素值来表示整个过程
注意：因为是拿后面柱子覆盖前面柱子，所以这里的示例的组合过程是由下向上的
以示例1为例
2 3 7 18 此时为一次完成阶梯 2 3 7 101 此时为一次完成阶梯 2 5 9 10 复制代码
以示例2为例
0 1 2 3 此时为一次完成阶梯 0 1 2 此时为一次完成阶梯 0 1 3 此时为一次完成阶梯 0 1 0 1 复制代码
以数组 [10,9,2,5,3,101,18,7,1,2] 为例
1 2 7 在更新下一次阶梯 1 3 7 在更新下一次阶梯 2 3 7 此时为一次完成阶梯 2 3 18 此时为一次完成阶梯 2 3 101 此时为一次完成阶梯 2 3 2 5 2 9 10 复制代码
以数组 [10,9,2,5,3,18,7,1,2,6,101] 为例
1 2 6 101 此时为一次完成阶梯 1 2 6 在更新下一次阶梯 1 2 7 在更新下一次阶梯 1 3 7 在更新下一次阶梯 2 3 7 此时为一次完成阶梯 2 3 18 此时为一次完成阶梯 2 3 2 5 2 9 10 复制代码
后续动画搞出来我再来更新
代码如下：
var lengthOfLIS = function(nums) { const pillars = [nums[0]]; let num = 1; for(let i = 1;i<nums.length;i++){ let cur = nums[i],l = 0,r = num-1; // 如果比现有最高的柱子还要高,放在末尾 if(cur>pillars[r]){ pillars[num] = cur; num++; }else{ // 二分查找合适的柱子 while(l<r){ const mid = (l+r) >> 1; if(pillars[mid]<cur) l = mid+1 else if(pillars[mid]>cur) r = mid else l = r = mid; } pillars[l] = cur; } } // 返回柱子数量 return num; }; 复制代码
提交后用时 70ms 左右，击败了 90+% 的用户，时间复杂度 是 O(nlogn) 的
最后祝大家周末愉快！但是也要记得学习哦！
如有任何问题或建议，欢迎留言讨论！
