欢迎来到DIVCSS5查找CSS资料与学习DIV CSS布局技术!
精读
 
什么是最长上升子序列?就是求一个数组中,最长连续上升的部分,如下图所示:
 
如果序列本身就是上升的,那就直接返回其本身;如果序列没有任何一段是上升的,则返回任何一个数字都可以。图中可以看到,虽然 3, 7, 22 也是上升的,但因为 22 之后接不下去了,所以其长度是有 3,与 3, 7, 8, 9, 11, 12 比起来,肯定不是最长的,因此找起来并不太容易。
 
在具体 DOM diff 场景中,为了保证尽可能移动较少的 DOM,我们需要 保持最长上升子序 不动,只移动其他元素。为什么呢?因为最长上升子序列本身就相对有序,只要其他元素移动完了,答案也就出来了。还是这个例子,假设原本的 DOM 就是这样一个递增顺序(当然应该是 1 2 3 4 连续的下标,不过对算法来说是否连续间隔不影响,只要递增即可):
 
如果保持最长上升子序不变,只需要移动三次即可还原:
 
其他任何移动方式都不会小于三步,因为我们已经最大程度保持已经有序的部分不动了。
 
那么问题是,如何将这个最长上升子序列找出来?比较容易想到的解法分别有:暴力、动态规划。
 
暴力解法
 
时间复杂度: O(2ⁿ)
 
我们最终要生成一个最长子序列长度,那么就来模拟生成这个子序列的过程吧,只不过这个过程是暴力的。
 
暴力模拟生成一个子序列怎么做呢?就是从 [0,n] 范围内每次都尝试选或不选当前数,前提是后选的数字要比前面的大。由于数组长度为 n,每个数字都可以选或不选,也就是每个数字有两种选择,所以最多会生成 2ⁿ 个结果,从里面找到最长的长度,即为答案:
 
这么傻试下去,必然能试出最长的那一段,在遍历过程中记录最长的那一段即可。
 
由于这个方法效率太低了,所以并不推荐,但这种暴力思维还是要掌握的。
 
动态规划
 
时间复杂度: O(n²)
 
如果用动态规划思路考虑此问题,那么 DP(i) 的定义按照经验为:以第 i 个字符串结尾时,最长子序列长度。
 
这里有个经验,就是动规一般 DP 返回值就是答案,字符串问题常常是以第 i 个字符串结尾,这样扫描一遍即可。而且最长子序列是有重复子问题的,即第 i 个的答案运算中,包括了前面一些的计算,为了不重复计算,才使用动态规划。
 
那么就看第 i 项的结果和前面哪些结果有关系了,为了方便理解如图所示:
 
假设我们看 8 这个数字,也就是 DP(4) 是多少。由于此时前面的 DP(0), DP(1) ... DP(3) 都已经算出来了,我们看看 DP(4) 和前面的计算结果有什么关系。
 
简单观察可以发现,如果 nums[i] > nums[i-1],那么 DP(i) 就等于 DP(i-1) + 1,这个是显而易见的,即如果 8 比 4 大,那么 8 这个位置的答案,就是 4 这个位置的答案长度 + 1,如果 8 这个位置数值是 3,小于 4,那么答案就是 1,因为前面的不满足上升关系,只能用 3 这个数字孤军奋战啦。
 
但仔细想想会发现,这个子序列不一定非要是连续的,万一第 i 项和第 i-2, i-3 项组合一下,也许会比与第 i-1 项组合起来更长哦?我们可以举个反例:
 
很显然,1, 2, 3, 4 组合起来是最长的上升子序列,如果你只看 5, 4,那么得出的答案只能是 4。
 
正是由于不连续这个特点,我们对于第 i 项,需要和第 j 项依次对比,其中 j=[0,i-1],只有和所有前项都比一遍,我们才放心,第 i 项找到的结果确实是最长的:
 
那么时间复杂度怎么算呢?动态规划解法中,我们首先从 0 循环到 n,然后对于其中每个 i,都做了一遍 [0,i-1] 的额外循环,所以计算次数是 1 + 2 + ... + n = n * (n + 1) / 2,剔除常数后,数量级是 O(n²)。
 
贪心 + 二分
 
时间复杂度: O(nlogn)
 
说实话,一般能想到动态规划解法就很不错了,再进一步优化时间复杂度就非常难想了。如果你没做过这道题,并且想挑战一下,读到这里就可以停止了。
 
好,公布答案了,说实话这个方法不像正常人类思维想出来的,具有很大的思维跳跃性,因此我也无法给出思维推导过程,直接说结论吧:贪心 + 二分法。
 
如果非要说是怎么想的,我们可以从时间复杂度上事后诸葛亮一下,一般 n² 时间复杂度再优化就会变成 nlogn,而一次二分查找的时间复杂度是 logn,所以就拼命想办法结合吧。
 
具体方案就一句话:用栈结构,如果值比栈内所有值都大则入栈,否则替换比它大的最小数,最后栈的长度就是答案:
 
先解释下时间复杂度,因为操作原因,栈内存储的数字都是升序的,因此可以采用二分法比较与插入,复杂度为 logn,外层 n 循环,所以整体时间复杂度为 O(nlogn)。另外这个方案的问题是,答案的长度是准确的,但栈内数组可能是错误的。如果要完全理解这句话,就得完全理解这个算法的原理,理解了原理才知道如何改进以得到正确的子序列。

如需转载,请注明文章出处和来源网址:http://www.divcss5.com/html/h63794.shtml