获取数组中的最长递增子序列——JS
站长
· 阅读数 13
Vue3 的 diff 逻辑中，利用了「最长递增子序列」的算法思维进行优化，从而大大缩减了 DOM 的移动成本。
本文讲解几种找寻数组中最长递增子序列的算法。
问题引入
首先带着问题来学习。
// 实现 getSequence 函数，找出 arr 的最长递增子序列
function getSequence(arr) {
//...
}
console.log(getSequence([1, 3, 0, 6])); // [1, 3, 6]
console.log(getSequence([1, 3, 5, 7, 11, 6, 12])); // [1, 3, 5, 7, 11, 12]
console.log(getSequence([3, 7, 11, 15, 9 , 11, 12]));
console.log(getSequence([3, 7, 22, 4, 8, 13, 9, 11, 12])); // [3, 7, 8, 9, 11, 12]
动态规划解法
动态规划的解决思路，借助一个 dp 数组去记录抵达各个数字时的递增序列长度，每个「数字 A」 的最长递增序列是它前面比该数字小的 「数字B」 的递增序列长度+1。
function getSequence(arr) {
const dp = new Array(arr.length).fill(1);
console.log({arr, dp});
for (let i = 1; i < arr.length; i++) {
for (let j = 0; j < i; j++) {
if (dp[j]+1 > dp[i]) {
dp[i] = dp[j]+1;
}
}
console.log({ arr, dp });
}
}
getSequence([3, 7, 22, 4, 8, 13, 9, 11, 12]);
运行看一下输出结果：
// 初始状态，dp 长度都为1
{"arr":[3,7,22,4,8,13,9,11,12],"dp":[1,1,1,1,1,1,1,1,1]}
// 遍历到数字7，往前找比它小的数字有3，所以7的递增序列长度是2
{"arr":[3,7,22,4,8,13,9,11,12],"dp":[1,2,1,1,1,1,1,1,1]}
// 遍历到数字22，往前找比它小的数字有3和7，选择7，得到的递增序列长度较大，为 3
{"arr":[3,7,22,4,8,13,9,11,12],"dp":[1,2,3,1,1,1,1,1,1]}
// 数字4，往前找比它小的数字只有3，所以4的递增序列长度是2
{"arr":[3,7,22,4,8,13,9,11,12],"dp":[1,2,3,2,1,1,1,1,1]}
// 数字8，往前找比它小的数字有3、7、4，其中7 和 4 递增序列长度最大，得到数字8最大长度为 3
{"arr":[3,7,22,4,8,13,9,11,12],"dp":[1,2,3,2,3,1,1,1,1]}
// 依次类推...
{"arr":[3,7,22,4,8,13,9,11,12],"dp":[1,2,3,2,3,4,1,1,1]}
{"arr":[3,7,22,4,8,13,9,11,12],"dp":[1,2,3,2,3,4,4,1,1]}
{"arr":[3,7,22,4,8,13,9,11,12],"dp":[1,2,3,2,3,4,4,5,1]}
{"arr":[3,7,22,4,8,13,9,11,12],"dp":[1,2,3,2,3,4,4,5,6]}
观察 dp 数组，可以发现最大值为 6。即最大的递增子序列长度为 6。如果题目只要求长度，那么已经得到了答案，可以尝试题目 「Leetcode 300. 最长递增子序列」。
但现在我们需要得到具体的递增序列，该怎么办？
假设最后答案为数组 result=[x, x, x, x, x, x]。观察 dp 数组值可以看到，数字 11 和 12 对应的 dp 值为 5 和 6，并且唯一，说明它们必定是最长递增序列的最后两位，即 result=[x, x, x, x, 11, 12]。
接着看 dp 值为 4 对应的 arr 数字，13 和 9。应该把哪个放入 result 中？
这里我们思考两个问题：
- 要放入 result 中的数，它是不是一定要比后一个数小（上述例子中要比 11 小）？因为它们需要满足「递增」性质。
- 如果有多个数字（上述例子中的 13 和 9，22 和 8）的 dp 值（即序列长度）相同，后面的数字是不是一定比前面的数字小？因为假如后面的数比前面的大，他们之间必定是满足「递增」关系，不可能出现 dp 值相同的情形。
这里我们通过思考可以知道，当遇到递增序列长度相同的数时，选择最后面的那个数，一定能让结果满足「递增」的条件。从而得到的结果为 result=[3, 4, 8, 9, 11, 12]。
根据上面的逻辑，我们可以通过倒序遍历 dp 来获得最长递增序列。完善 getSequence 函数如下所示：
// 实现 getSequence 函数，找出 arr 的最长递增子序列
function getSequence(arr) {
const dp = new Array(arr.length).fill(1);
for (let i = 1; i < arr.length; i++) {
for (let j = 0; j < i; j++) {
if (arr[j] < arr[i] && dp[j]+1 > dp[i]) {
dp[i] = dp[j]+1;
}
}
// console.log({ arr, dp });
}
let max = Math.max(...dp);
const result = [];
for (let i = arr.length-1; max > 0; i--) {
if (dp[i] === max) {
result.unshift(arr[i]);
max--;
// console.log({result});
}
}
return result;
}
// 测试验证
console.log(getSequence([1, 3, 0, 6])); // [1, 3, 6]
console.log(getSequence([1, 3, 5, 7, 11, 6, 12])); // [1, 3, 5, 7, 11, 12]
console.log(getSequence([3, 7, 11, 15, 9, 11, 12])); // [ 3, 7, 9, 11, 12 ]
console.log(getSequence([3, 7, 22, 4, 8, 13, 9, 11, 12])); // [3, 7, 8, 9, 11, 12]
优化算法
上述解法在构建 dp 数组的时候，采用了两层循环的方式，效率较差。我们可以增加一个数组来保存当前的递增序列，利用二分搜索优化 dp 的构建。
继续以 arr = [3, 7, 22, 4, 8, 13, 9, 11, 12] 为例。构造 result 和 dp 的过程如下所示：
// 遍历完前面三个数后，dp 及 result 结果如下：
{
arr: [ 3, 7, 22, 4, 8, 13, 9, 11, 12 ]
dp: [ 1, 2, 3, 1, 1, 1, 1, 1, 1 ],
result: [ 3, 7, 22 ]
}
// 接下来遍历是 4， 发现比 22 小，通过二分查找，找到它应该在 3 的后面，替换掉 7，记录它的 dp 值为 2。
// 这里替换的原因是，我们可以认为 4 比 7 小，它的潜力要更大。假如下一个数字是 5，我们可以把它放在 4 后面，得到 5 的 dp 值为 3。
// 如果 4 没有替换 7，那 5 就只能放在 3 后面，得到的 dp 值为 2，显然 4 的潜力要更大。
{
arr: [ 3, 7, 22, 4, 8, 13, 9, 11, 12 ]
dp: [ 1, 2, 3, 2, 1, 1, 1, 1, 1 ],
result: [ 3, 4, 22 ]
}
// 下一个数字是 8，比 22 小，找到 result 中比它小的数字是 4，从而放在 4 后面，得到 dp 值为 3
{
arr: [ 3, 7, 22, 4, 8, 13, 9, 11, 12 ]
dp: [ 1, 2, 3, 2, 3, 1, 1, 1, 1 ],
result: [ 3, 4, 8 ]
}
// 接下来是 13， 比 8 大，直接进入数组，得到 dp 值为 4
{
arr: [ 3, 7, 22, 4, 8, 13, 9, 11, 12 ]
dp: [ 1, 2, 3, 2, 3, 4, 1, 1, 1 ],
result: [ 3, 4, 8, 13 ]
}
// 9， 比 8 大，替换 result 中的 13，得到 dp 值为 4
{
arr: [ 3, 7, 22, 4, 8, 13, 9, 11, 12 ]
dp: [ 1, 2, 3, 2, 3, 4, 4, 1, 1 ],
result: [ 3, 4, 8, 9 ]
}
// 11 跟 12 都直接进入 result， 得到 dp 值为 5 和 6
{
arr: [ 3, 7, 22, 4, 8, 13, 9, 11, 12 ]
dp: [ 1, 2, 3, 2, 3, 4, 4, 5, 6 ],
result: [ 3, 4, 8, 9, 11, 12 ]
}
按照上面的逻辑，我们得到了 dp 数组。需要注意的是虽然现在看到的 result 数组就是我们所需要的结果，但假如 arr 数组是[ 3, 7, 22, 4, 8, 13, 9, 11, 12, 1 ]，得到的 result 会是 [ 1, 4, 8, 9, 11, 12 ]，很明显这是错误的子序列，不是正确答案。
所以最终还是需要同前文算法一样，遍历一遍 dp，构造最终的 result 数组。整体代码实现如下所示：
function getSequence(arr) {
const dp = new Array(arr.length).fill(1);
const result = [arr[0]];
for (let i = 1; i < arr.length; i++) {
// 如果这个数大于 result 的最后一个数，直接插入
if (arr[i] > result[result.length-1]) {
result.push(arr[i]);
dp[i] = result.length;
} else {
// 否则，通过二分查找找到该数字应该在的位置，从而得到 dp
let l = 0, r = result.length-1, m = Math.floor((l+r)/2);
while (l <= r) {
if (result[m] < arr[i]) {
l = m + 1;
} else {
r = m - 1;
}
m = Math.floor((l + r) / 2);
}
result[l] = arr[i];
dp[i] = l+1;
}
}
// result 不一定是正确的最长递增序列，中间有些数有可能被替换了
// 所以需要再走一遍构建 result 的逻辑
let max = Math.max(...dp);
for (let i = arr.length-1; max > 0; i--) {
if (dp[i] === max) {
result[max-1] = arr[i];
max--;
}
}
return result;
}
另一种优化算法
还有另外一种解决思路，同样利用 result 数组及二分法，但是去掉 dp 数组，采用 p 数组来记录每个数字对应的前一个数字。
还需要进行调整的思路是，这次算法中的 result 和 p 只记录对应 arr 中的下标，不记录具体数字，以利于后续进行查找。
继续以 arr = [3, 7, 22, 4, 8, 13, 9, 11, 12] 为例。构造 result 和 p 数组的过程如下所示：
// 从第二个数 7 开始，7 的前一位数是 3， 所以 p 数组对应位置记录 3 的下标 0
{
arr: [ 3, 7, 22, 4, 8, 13, 9, 11, 12 ]
p: [ 0, 0 ],
result: [ 0, 1 ]
}
// 22, 前一位是 7，p 对应位置记录 7 的下标 1
{
arr: [ 3, 7, 22, 4, 8, 13, 9, 11, 12 ]
p: [ 0, 0, 1 ],
result: [ 0, 1, 2 ]
}
// 4, 通过二分法查找，替换7，4在序列中的前一个数字是3，p对应位置记录 3 的下标 0，result 中 4 的下标替换 7 的下标
{
arr: [ 3, 7, 22, 4, 8, 13, 9, 11, 12 ]
p: [ 0, 0, 1, 0 ],
result: [ 0, 3, 2 ]
}
// 接下来是 8, 通过二分法查找，替换22，在序列中的前一个数字是4，p对应位置记录 4 的下标 3, result 中 8 的下标 4 替换 22 的下标 2。
{
arr: [ 3, 7, 22, 4, 8, 13, 9, 11, 12 ]
p: [ 0, 0, 1, 0, 3 ],
result: [ 0, 3, 4 ]
}
// 依次类推，最终结果如下：
{
arr: [ 3, 7, 22, 4, 8, 13, 9, 11, 12 ]
p: [ 3, 0, 1, 0, 3, 4, 4, 6, 7 ],
result: [ 0, 3, 4, 6, 7, 8 ]
}
从上一节我们知道 result 不一定是正确的答案，需要进行纠错。但是我们可以确定，result 的最后一个数字一定是正确的，借助 p 数组，找到最后一个数字对应的前一个数字，替换 result 中的值，然后再根据该值找到前一位数字，依次替换，就能得到最终的结果了。
具体实现代码如下：
// 实现 getSequence 函数，找出 arr 的最长递增子序列
function getSequence(arr) {
const p = arr.slice();
const result = [0];
for (let i = 1; i < arr.length; i++) {
// 如果这个数大于 result 的最后一个数，直接插入 result 中，并在 p 中记录前一个数
if (arr[i] > arr[result[result.length-1]]) {
p[i] = result[result.length-1]
result.push(i);
} else {
// 否则，通过二分查找找到该数字应该在的位置，进行替换，在 p 中记录前一个数
let l = 0, r = result.length-1, m = Math.floor((l+r)/2);
while (l <= r) {
if (arr[result[m]] < arr[i]) {
l = m + 1;
} else {
r = m - 1;
}
m = Math.floor((l + r) / 2);
}
result[l] = i;
p[i] = result[l-1];
}
// console.log({ p, result });
}
// result 不一定是正确的最长递增序列，中间有些数有可能被替换了
// 倒序遍历 result，根据 p 替换前面的数
let u = result.length, v = result[u-1];
while (u > 0) {
u--;
result[u] = arr[v];
v = p[v];
}
return result;
}
console.log(getSequence([1, 3, 0, 6])); // [1, 3, 6]
console.log(getSequence([1, 3, 5, 7, 11, 6, 12])); // [1, 3, 5, 7, 11, 12]
console.log(getSequence([3, 7, 11, 15, 9, 11, 12])); // [ 3, 7, 9, 11, 12 ]
console.log(getSequence([3, 7, 22, 4, 8, 13, 9, 11, 12])); // [3, 7, 8, 9, 11, 12]