最长递增子序列

本节目标：理解“最长递增子序列”的核心思路，并能把它用于实际开发或面试表达。将连续递增子序列保持不动，只插入那些不符合递增子序列的元素，将提高渲染效率；比如[5,3,4,0]，当碰到索引为1和2的元素，我们直接跳过，只在索引为0和3的时候，分别插入元素5和0；

假如有列表：3 2 8 9 5 6 7 11 15 ；
求最长递增子序列的个数，要点是：

贪心算法；

二分查找：用在递增序列中；

思路就是当前这一项比我们最后一项大则直接放到末尾；

如果当前这一项比最后一项小，需要在序列中通过二分查找找到比当前项大的第一项，用当前项替换它；

最优的情况，就是默认递增。

查找过程：

2,8

2,8,9

2,5,9

2,5,6

2,5,6,7,11,15

结果为：2 5 6 7 11 15

假如列表为：3 2 8 9 5 6 7 11 15 4；按上面的思路会得到： 2 4 6 7 11 15 这样就有bug，但至少得到的最长递增子序列的元素个数是对的，就是有6个元素；

function getSequence(arr) {
  const len = arr.length;
  // 以默认第0项为基准来做序列，存放的是索引
  const result = [0];
  let resultLastIndex;
  // 二分查找用到的变量
  let start, end, middle;
  for (let i = 0; i < len; i++) {
    let arrI = arr[i]
    // 因为vue里面的序列中的0意味着没有意义，表示需要创建
    if (arrI !== 0) {
      // 结果序列的最后一项，它是索引
      resultLastIndex = result[result.length - 1];
      if (arr[resultLastIndex] < arrI) {
        // 当前项比我们最后一项大则直接放到末尾；
        result.push(i);
        continue
      }
      // 下面的情况是当前项比最后项小的情况
      // 通过二分查找，在结果集中找到比当前值大的，用当前值的索引将其替换掉
      // 递增序列采用二分查找是最快的
      // 二分查找要有个开始指针，一个结束指针，还要找个中点
      start = 0;
      end = result.length - 1;
      // 如：2,3,4,5,6,7,8，当前项是6，
      // 数组的长度不是奇数，就是偶数，考虑长度为0，1，2，3
      // start===end的时候就结束了
      // 所以数组至少得2个元素
      while (start < end) {
        // 先算middle
        // 再比较middle所在值和当前值的大小关系
        // 最后移动Start和end指针
        middle = ((start + end) / 2) | 0;
        // 6,7,8,middle:1,start:0,end:2
        // 6,7,middle:0，移动后指针:start:0,end===middle===start===0
        // 分到后面，数组要不就是4个元素，再分成2个
        // 要不就是3个元素再分成2个和1个，即2个元素或1个元素的情况
        // 如果是2个元素，算出middle再分一下，就成了1个元素
        // 这时，Start===end，结束循环
        // 当前值比中间值大
        if (arr[result[middle]] < arrI) {
          // 移动开始指针
          start = middle + 1
        } else {
          // 有相等的情况?vue中的key不能重复，所以不会出现相等的情况
          // 就算是相等的情况也可以?
          end = middle
        }
      }
      // middle最后要不等于，大于或小于当前项
      if (arr[result[end]] > arrI) {
        // 我们用当前项的索引替换中间项
        result[end] = i
      }
    }
  }
}

特点： key不会重复；比如列表： 1，7，8，9，2，3，4，5，6，0 按思路会得到0，2，3，4，5，6，很明显，原列表中无法有这样的递增序列；但至少正确的递增序列的个数与这个列表是相同的；因为我们在替换之前的列表肯定是正确的；因为它是由小到大排出来的；当出现一个比最末元素小的数字的时候，我们拿这个更小的数字去替换之前的正确列表，无疑，新列表的数量自然是正确的；

接下来的问题是，我们如何得到正确的列表？在刚开始的递增序列中，一切都正常，都是对的；当出现一个比生成列表最末元素小的元素的时候，我们肯定想，之前的列表可能是有问题的；

我们要重新得到一个列表，这个列表从哪里开始呢？我们用二分法找到比当前元素大的最小数字，我们要替换它，因为在正确的列表中，它是不可能出现的，正确的列表应该是比之前列表中，比当前元素小的部分加上当前元素，再加上比当前元素大的部分；

我们用列表3 2 8 9 5 6 7 11 15 4验证一下; 刚开始是3，接下来出现了2，那么对于递增列表来说，肯定不能3开头，要从2开头才对，所以我们把3换成了2；接下来出现了8，和9，得到2，8，9的递增序列；

接下来我们出现的元素可能会出现比列表中已有元素小的数字，这个数字一旦出现，我们元素的列表就必须是：

原列表中比出现元素小的部分，加上

当前元素，

再加上比当前元素大的剩余部分

至于比当前元素大的最小整数，要用当前元素替换掉才对；

这样就得到了：比当前元素小的序列，当前元素，比当前元素大的序列；

这里出现一个问题，比当前元素小的序列+当前元素是没有问题的，但如果再加上比当前元素大的部分，就会出问题，因为我们把当前元素移动到列表中出现过的元素之前，这样明显和原来的列表不一样的；如果列表是：3，2，8，9，5 当我们得到2，8，9时，出现了5，我们得到比当前元素小的序列+当前元素，没有问题，再加上比当前元素大的部分，得到2，5，9，这时，5移动到了9之前，和原列表顺序小合的，我们要想办法得到正确的；

此外，一直使用小的数字替换前面的数字也有问题，难道后面出现小的数字，我前面的都要作废吗，万一后面只有一个数字了呢，那我前面大数字开头的超过1个元素的列表就作废了吗？

采用的方法是，新建一个和原序列一样长的数组，记下每个元素前面的元素的索引；当我们碰到3时，我们得到列表3，记下3之前的元素的索引，由于3是首元素，所以应该是[undefined]；接下来碰到2，2比之前的列表的末元素要小，之前的列表无效，我们要得到比当前元素小的序列+当前元素，由于没有比当前元素小的序列，我们得到的序列是当前元素，也就是2，要进行的操作是用2来替换掉3，这时我们再看一下2之前的元素的索引，还是[undefined]；

接下来出现8，没有比列表2的最末元素2要大，所以我们得到了2，8，记录下8前面元素的索引

最长递增子序列 ​

最长递增子序列