关于算法:最长的递增子序列的算法推演

4次阅读

共计 3119 个字符，预计需要花费 8 分钟才能阅读完成。

例子：3 1 2 7 5 8 6 9 4

从前到后循坏，找到所有的可能性

const arr = [3, 1, 2, 7, 5, 8, 6, 9, 4]
for (let i = 0; i < arr.length; i++) {const n = arr[i]
    console.log(i, n)
    // todo
}

i = 0，可能最长组合：

3 ... // i = 0, n = 3

i = 1，可能最长组合：

3 ... // i = 0, n = 3
1 ... // i = 1, n = 1

i = 2，可能最长组合：

3 ...   // i = 0, n = 3
1 ...   // i = 1, n = 1
1 2 ... // i = 2, n = 2

由此类推：
i = 9，最终组合：

0 1 2 3 4 // 序号

3         // i = 0, n = 3
1         // i = 1, n = 1
1 2       // i = 2, n = 2
1 2 7     // i = 3, n = 7
1 2 5     // i = 4, n = 5
1 2 7 8   // i = 5, n = 8
1 2 5 8
1 2 5 6   // i = 6, n = 6
1 2 7 8 9 // i = 7, n = 9
1 2 5 8 9
1 2 5 6 9
1 2 4     // i = 8, n = 4

找到了最长的递增子序列为 1 2 7 8 9，1 2 5 8 9，1 2 5 6 9

咱们能够发现

1 2 7 ...
1 2 5 ...

1 2 5 能带来的可能，蕴含了 1 2 7 能带来的所有可能

1 2 5 8 ...
1 2 5 6 ...

1 2 5 6 能带来的可能，蕴含了 1 2 5 8 能带来的所有可能

所以咱们只须要用到雷同序号下的最小值

以 i = 5, n = 8 为例：

0 1 2 // 序号

3 ...
1 ...
1 2 ...
1 2 7 ...
1 2 5 ...

变成

3 ...
1 ...
1 2 ...
1 2 7 ...
1 2 5 ...
1 2 5 8 ...

序号 2，对应的值 [7, 5]，最小值是 5，这里只需用到 1 2 5

下面最终组合：

3         // i = 0, n = 3
1         // i = 1, n = 1
1 2       // i = 2, n = 2
1 2 7     // i = 3, n = 7
1 2 5     // i = 4, n = 5
1 2 5 8   // i = 5, n = 8
1 2 5 6   // i = 6, n = 6
1 2 5 6 9 // i = 7, n = 9
1 2 4     // i = 8, n = 4

找到了最长的递增子序列为 1 2 5 6 9，数据过大时，大大降低了循环次数

留神：如果是要找到所有的可能性，只能就义性能，但很多时候，咱们只须要找到其中最长的一种可能就行了，比方：vue 的虚构节点比照

后面中，每次都须要先找到对应序号下最小的一位，而后再来比照，其实咱们能够把每个序号上面的最小值用一个数组（min_arr）记录下来

0 1 2 3 4 // 序号

3         // i = 0, n = 3, min_arr = [3]
1         // i = 1, n = 1, min_arr = [1]
1 2       // i = 2, n = 2, min_arr = [1, 2]
1 2 7     // i = 3, n = 7, min_arr = [1, 2, 7]
1 2 5     // i = 4, n = 5, min_arr = [1, 2, 5]
1 2 5 8   // i = 5, n = 8, min_arr = [1, 2, 5, 8]
1 2 5 6   // i = 6, n = 6, min_arr = [1, 2, 5, 6]
1 2 5 6 9 // i = 7, n = 9, min_arr = [1, 2, 5, 6, 9]
1 2 4     // i = 8, n = 4, min_arr = [1, 2, 4, 6, 9]

由 v2.0.0 可知，咱们只须要和每个序号下最小值来比照，也就是以后 n 间接和 min_arr 比照

思路：

如果以后 n 比 min_arr 最初一项大，则间接放到开端，如：i = 3, n = 7，7 比 2 大，7 间接放在 2 的前面
如果以后 n 比 min_arr 最初一项小，从后往前循环 min_arr，找到比 n 小的一项为止，n 放在其前面，此时原前面这一项必定比 n 大，所以替换原前面这一项；如：i = 8, n = 4，始终往前找，2 比 4 小，进行循环，4 放在 2 前面，2 前面原来的 5 必定是比 4 大的，不然到 5 就应该完结了，所以间接替换原来的 5（ 代码中会采纳二分法查找 ）

此时咱们发现最终失去的 min_arr 的值尽管是不正确的，然而最初一位的值必定是正确的，如果咱们转变思维，标记最初一位在谁的前面，而后一层一层的往前标记，这个事件是不是就成了，如

0 1 2 3 4 // 序号

3         // i = 0, n = 3, min_arr = [3], 3 后面为 undefined
1         // i = 1, n = 1, min_arr = [1], 1 后面为 undefined
1 2       // i = 2, n = 2, min_arr = [1, 2], 2 后面为 1
1 2 7     // i = 3, n = 7, min_arr = [1, 2, 7], 7 后面为 2
1 2 5     // i = 4, n = 5, min_arr = [1, 2, 5], 5 后面为 2
1 2 5 8   // i = 5, n = 8, min_arr = [1, 2, 5, 8], 8 后面为 5
1 2 5 6   // i = 6, n = 6, min_arr = [1, 2, 5, 6], 6 后面为 5
1 2 5 6 9 // i = 7, n = 9, min_arr = [1, 2, 5, 6, 9], 9 后面为 6
1 2 4     // i = 8, n = 4, min_arr = [1, 2, 4, 6, 9], 4 后面为 2

先找到 9，而后 6，而后 5，而后 2，而后 1，此时就找到了最长的递增子序列为 1 2 5 6 9

在程序中咱们须要把值对应成索引，能力更好的找到其地位

0 1 2 3 4 5 6 7 8 // 索引
3 1 2 7 5 8 6 9 4 // 值

下面 v4.0.0 变成

0 1 2 3 4 // 序号

0         // i = 0, min_arr = [0], 0 后面为 undefined
1         // i = 1, min_arr = [1], 1 后面为 undefined
1 2       // i = 2, min_arr = [1, 2], 2 后面为 1
1 2 3     // i = 3, min_arr = [1, 2, 3], 3 后面为 2
1 2 4     // i = 4, min_arr = [1, 2, 4], 4 后面为 2
1 2 4 5   // i = 5, min_arr = [1, 2, 4, 5], 5 后面为 4
1 2 4 6   // i = 6, min_arr = [1, 2, 4, 6], 6 后面为 4
1 2 4 6 7 // i = 7, min_arr = [1, 2, 4, 6, 7], 7 后面为 6
1 2 8     // i = 8, min_arr = [1, 2, 8, 6, 7], 8 后面为 2

先找到索引 7，而后 6，而后 4，而后 2，而后 1，此时索引为 1 2 4 6 7，对应的最长的递增子序列值为 1 2 5 6 9

function getSequence(arr:number[]) {
  const len = arr.length
  const min_arr = [0] // 存储最小的索引，以索引 0 为基准
  const prev_arr = arr.slice() // 贮存后面的索引，slice 为浅复制一个新的数组
  let last_index
  let start
  let end
  let middle
  for (let i = 0; i < len; i++) {let arrI = arr[i]
    // 1. 如果以后 n 比 min_arr 最初一项大
    last_index = min_arr[min_arr.length - 1]
    if (arr[last_index] < arrI) {min_arr.push(i)
      prev_arr[i] = last_index // 后面的索引
      continue
    }
    // 2. 如果以后 n 比 min_arr 最初一项小（二分类查找）start = 0
    end = min_arr.length - 1
    while(start < end) {middle = (start + end) >> 1 // 相当于 Math.floor((start + end)/2)
      if (arr[min_arr[middle]] < arrI) {start = middle + 1} else  {end = middle}
    }
    if (arr[min_arr[end]] > arrI) {min_arr[end] = i
      if (end > 0) {prev_arr[i] = min_arr[end - 1] // 后面的索引
      }
    }
  }

  // 从最初一项往前查找
  let result = []
  let i = min_arr.length
  let last = min_arr[i - 1]
  while(i-- > 0) {result[i] = last
    last = prev_arr[last]
  }

  return result
}

console.log(getSequence([3, 1, 2, 7, 5, 8, 6, 9, 4]))
// 索引：[1, 2, 4, 6, 7]
// 值：[1, 2, 5, 6, 9]

正文完