乐趣区

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

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

v1.0.0

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

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

v2.0.0

咱们能够发现

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 的虚构节点比照

v3.0.0

后面中,每次都须要先找到对应序号下最小的一位,而后再来比照,其实咱们能够把每个序号上面的最小值用一个数组(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 比照

思路:

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

v4.0.0

此时咱们发现最终失去的 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]
退出移动版