-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathalgorithm.ts
51 lines (50 loc) · 1.79 KB
/
algorithm.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// https://en.wikipedia.org/wiki/Longest_increasing_subsequence
export function getSequence(arr: number[]): number[] {
const preArr = arr.slice(0) // 前驱节点的索引数组，用于回溯正确的顺序
const result = [0]
let lastIndex, // 结果数组最后一项存的索引值
start,
end,
middle
const len = arr.length
// 如果比当前末尾大则追加，比末尾小则二分查找进行替换
// 算出来的结果数组长度是对的，顺序不对
for (let i = 0; i < len; i++) {
const arrI = arr[i] // 每一项的值
if (arrI !== 0) {
lastIndex = result[result.length - 1]
if (arr[lastIndex] < arrI) {
preArr[i] = lastIndex // 记录结果数组
// 如果比最后一项大，加入结果数组并 continue
result.push(i)
continue
}
// 二分查找 替换元素
start = 0
end = result.length - 1
while (start < end) {
middle = (start + end) >> 1 // 中间的索引
if (arr[result[middle]] < arrI) {
start = middle + 1 // 找右半部分
} else {
end = middle // 找左半部分
}
}
if (arrI < arr[result[start]]) {
if (start > 0) {
preArr[i] = result[start - 1] // 找到索引进行记录
}
result[start] = i // 找到更有潜力的数组进行替换（贪心算法）
}
}
}
// 通过前驱节点找到正确的调用顺序
let resultLen = result.length
let current = result[resultLen - 1] // 取出最后一个
// 通过最后一项 向前查找
while (resultLen-- > 0) {
result[resultLen] = current // 最后一项肯定是正确的
current = preArr[current] // 当前记录的索引就是上一个项
}
return result
}