由于SFMarkdown编辑器不支持标签图片，文章中的图片无法显示。为了更好的阅读体验，可以到推荐阅读地址：点击跳转在精读《DOM diff 原理》一文中，我们提到Vue使用贪心+二分算法求最长上升子序列，但并未深究原理这个算法，所以专门开一章来详细讲解。另外，作为一道算法题，最长上升子序列很经典，在工业界也很实用，难度也很大，希望大家一定要掌握。精读什么是最长的上升子序列？就是找一个数组中最长的连续上升部分，如下图：-900-310.png">如果序列本身是升序的，则直接返回自身；如果序列中没有任何部分是升序的，则返回任何数字。从图中可以看出，虽然3、7、22也在上升，但是因为不能在22之后继续，所以他们的长度是3。和3、7、8、9、11、12相比，肯定不是最长，所以不容易找到。在特定的DOMdiff场景下，为了保证移动尽可能少的DOM，我们需要保持最长的升序子序列不变，只移动其他元素。为什么？因为最长的升序子序列本身是比较有序的，只要移动其他元素，答案就出来了。还是这个例子，假设原来的DOM是这样的递增顺序（当然应该是1234个连续的下标，但是不影响算法区间是否连续，只要递增）：如果保持最长升序列不变，只需要移动三次恢复：任何其他移动方法都会不少于三步，因为我们已经订购的零件已经尽量保留了下来。那么问题来了，如何找出这个最长的上升子序列呢？比较容易想到的方案是：暴力和动态规划。暴力解的时间复杂度：O(2?)我们最终要生成最长的子序列长度，所以我们来模拟生成这个子序列的过程，但是这个过程是暴力的。暴力模拟如何产生子序列？就是每次从[0,n]范围内尝试选择或不选择当前的数，前提是后面选择的数比前面的大。由于数组的长度为n，每个数可以选也可以不选，即每个数有两个选择，所以最多会产生2?个结果，从中找出最长的长度，就是答案：如果你一直这么傻的尝试，你一定能尝试最长的部分。只记录遍历过程中最长的那一段。因为这种方法效率太低，所以不推荐，但是这种暴力思维还是需要掌握的。动态规划时间复杂度：O(n2)如果用动态规划的思想来考虑这个问题，那么DP(i)的定义经验上就是：第i个字符串结束时最长子序列的长度。这里有个经验，就是动态规则的DP返回值就是答案。字符串题往往以第i个字符串结尾，扫一遍就可以了。而且最长的子序列有重复的子问题，即第i个答案的计算包含了之前的一些计算。为了不重复计算，采用了动态规划。然后看第i项的结果和前面结果的关系，如图，方便理解：6000000002698-2-tps-900-164.png">假设我们看数字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(n2)。贪心+二元时间复杂度：O(nlogn)说实话，一般想到动态规划的解法还是不错的，但是进一步优化时间复杂度就非常困难了。如果你还没有做过这道题，想挑战一下，可以到此为止。好了，答案揭晓。说实话，这个方法不像是正常人的思维想出来的。它有很多思维跳跃，所以不能给出思维推导过程，就说结论吧：贪心+二分法。如果一定要说我们的想法，我们可以从时间复杂度上事后想想。一般n2的时间复杂度再优化一下就会变成nlogn，而二分查找的时间复杂度是logn，所以我们就拼命的想办法结合起来。酒吧。具体解决办法就一句话：使用栈结构，如果值大于栈中所有值，则入栈，否则替换比它大的最小数，长度为finalstack就是答案：先说明一下时间复杂度。由于操作原因，栈中存储的数字是按升序排列的，所以可以使用二分法比较和插入，复杂度为logn，外层循环n次，所以整体时间复杂度为O(nlogn)。这个解决方案的另一个问题是答案的长度是准确的，但堆栈中的数组可能是错误的。要想完全理解这句话，就必须完全理解这个算法的原理。只有理解了原理，才能知道如何改进才能得到正确的子序列。那我就得解释一下原理了。初思并不复杂，可以边喝茶边看。首先，我们要有一个直观的认识，就是为了让最长的上升子序列尽可能的长，就要尽量保证所选数的增长速度尽可能慢，反之反之亦然。比如我们选择的数字是0、1、2、3、4，那么这种贪心是比较稳定的，因为它增长得越慢越好，后面遇到的大概率可以算进去。但是如果我们选择0、1、100，那么我们在选择100的时候就应该慌张了，因为如果我们把它增加到100，那不就把100以内的所有数字都舍弃了吗？这个时候索要100未必是明智的选择，丢了可能以后的空间会更大。这实际上是一种贪婪的思维。所谓局部最优解就是全局最优解。但是上面的想法显然是不完整的。我们继续想，如果读完0、1、100后没有数，那么100还是可以放进去的，虽然100很大，但毕竟是最后一位。还是有用的。所以从左向右遍历的时候，遇到比较大的数的时候，应该放在最前面。重点是，如果继续倒着读，读到一个小于100的数，怎么办？如果到这里不能进行思维的飞跃，分析就只能到此为止了。你可能认为你可以继续分析。比如遇到5，显然要挤出100，因为0,1,5和0,1,100的长度都是3，但是0,1,5的“势”明显大于0、1、100，所以长度不变，一个潜力更大，必须换！这个思路是对的，但是换个场景，如果遇到3、7、11、15，这时候遇到9，怎么变？如果考虑潜力的话，3、7、9的潜力最好，但是从4到3就牺牲了长度，以后会不会没有比9大的就不知道了。如果不是，这个长度就没有原来的那么长了4如果出于长度的考虑，还留着3,7,11,15，如果后面连续出现几个10,12,13,14你会傻眼的，你会觉得有点短视。那么问题来了，接下来的号怎么处理，才不会在以后目光短浅，“抓住稳稳的幸福”。这里开始出现跳转思维，答案就是上面方案中提到的“如果该值大于栈中所有的值，则将其压入栈中，否则替换比它大的最小数”。这是一个思维的飞跃。实现现在和未来的核心是牺牲堆栈内容的正确性，保证总长度的正确性，让每一步都能抓住未来最好的机会。只有总长度正确才能保证最长序列。至于牺牲栈内容的正确性，确实是一个很大的代价，但换来的是未来的可能，至少长度可以得到正确的结果。如果内容也是正确的话，可以加一些辅助手段来解决，后面再说。所以总的来说，这种牺牲是非常值得的。下图会介绍为什么牺牲栈内容的正确性可以换来正确的长度，抢占未来先机。举个极端的例子：3,7,11,15,9,11,12，如果坚持一开始找的3,7,11,15，长度只有4，但是如果放弃11,15,把3,7,9,11,12连在一起，长度比较好。按照贪心算法，我们会先依次遇到371115。由于每个数都比前一个大，所以也没什么好想的，直接塞进栈：!6000000000883-2-tps-704-256.png">遇见9的时候很美好，这时候9还不是最大的。为了把握稳定的幸福感，我们简单地把略大于9的11换掉会怎样？首先数组的长度没有变化，因为替换操作不会改变数组的长度。这时候如果9后面没有值，我们就不会输。此时输出长度4仍然是最优答案。我们继续，下一步遇到11的时候，我们还是替换比它稍微大一点的15：-2-tps-704-456.png">此时我们把最后一个数字替换掉，发现3,7,9,11终于是一个合理的序列，长度和3,7,11,15一样，但它有更多的潜力，接下来的12应该放在最后，最后的答案是：5。其实这个算法的本质这里并没有说清楚。我们还是回到3,7,9,15这一步，找出为什么9可以代替11。假设9后面跟着一个大的99，那么下一步直接把99追加到最后：此时我们得到了3,7,9,15,99，但是如果你仔细看，你会发现在原来的序列中9是在15的后面，因为我们的插入导致9放在了15的前面，所以这显然不是正确答案，但是长度是正确的，因为这个答案相当于我们选择了3、7、11、15、99！为什么可以这么理解呢？因为只要不替换最后一个数字，我们心目中的队列其实就是原来的队列。即只要栈没有被替换，新插入的值总是充当占位符，目的是让新值可以方便的插入，但是如果真的没有新值可以插入，那么虽然栈内容是错误的，但至少长度是正确的，因为9在替换没有完成的时候，其实不是9，只是一个占位符，后面的值还是11。所以不管怎么改，只要最后一个不是替换，替换操作将无效。再举个例子：可以看出1，2、3、4不能完全替代7、8、9、10、11，所以最后的结果是1、2、3、4、11，不过没关系，只要替代没有完成，答案是7、8、9、10、11，但是我们没有记录，但是如果只看长度的话，两者是没有区别的，所以是没有问题的。1、2、3、4、5、6呢？让我们看看替换后会发生什么：可以看到，当用5代替时，这个数列的顺序是正确的，因为1,2,3,4,5完全可以代替7,8,9,10,11，而且势比它大，我们找到了最优部分解。所以1,2,3,4,11这里1,2,3,4就像卧底特工。11还在的时候，他们还是咽了口口水，把7、8、9、10、11叫老大（其实1个7叫老大，2叫8个老大，以此类推），但是当5进来的时候，1，2、3、4、5可以对战7、8、9、10、11，因为它的实力已经超越了原boss的实力。我们之前所做的看似微不足道的更换，其实是在不断寻找未来可能的最佳解决方案，直到有光明前景的那一天。若无明日，当弟也好，长犹正；早期会更新最大长度，所以这种贪心可以兼顾正确性和效率。最后，让我们看看如何在找到答案的同时找到正确的序列？其实看完这个大家应该也能猜出来了，不用说了，前面说过了，只要最后一个被替换或者插入，那么栈的顺序就是正确的。所以我们可以在替换最后一个或者插入的时候，存储一份当前栈的副本，??这样最后剩下的副本就是最终正确的顺序。那么为什么会这样呢？最后，我们用一个例子来加强理解，因为我们已经很熟练了，所以合并前面的步骤：6000000000471-2-tps-1200-344.png">到目前为止，7、8、9、13是不存在的，其实指的是10、11、12、13，之前已经解释过了，只是不再.我们此时已经存储了队列10、11、12、13，所以这个队列到此结束时的输出是正确的。我们看下一步：为了方便识别，我给不同分组的数字加上背景色，这样比较容易观察：我们发现由于每次替换都是一个比它稍大的数字，一旦遇到比较小的起始1,2,3,4,5，即使是之前的Rounds7,8,9也没有完全替换掉10,11,12,13，必须从最左边开始替换较小的，因为栈中的数字是单调递增的。然后全部替换完成，或者从某个数开始，向右替换完成。这时，队列中的号码必须是正确的相对顺序。从这个例子来看，2、3肯定会先替换8、9，替换13时，出栈的相对顺序必须符合原数组的相对顺序。最后看一个比较复杂的例子加深印象：读到这里，恭喜你，你已经大功告成了，完全理解了DOMdiff算法。那么Vue为了贪心计算最长的上升子序列付出了多少代价呢？其实就是O(n)和O(nlogn)的关系。我们看图：可以看出O(nlogn)时间复杂度增长趋势勉强可以接受，尤其是在工程场景中，一个父节点的子节点数量不能太多，也不会占用太多分析时间更多的好处是数量最少DOM运动。是算法与工程实践比较完美的结合。讨论地址为：Jingdu《DOM diff 最长上升子序列》·Issue#310·dt-fe/weekly想参与讨论的请戳这里，每周都有新话题，周末或周一发布。前端精读——帮你过滤靠谱的内容。关注前端精读微信公众号版权声明：免费转载-非商业-非衍生保留属性（CreativeCommons3.0License）
