发布于2020-11-29
上次编辑2021-04-19
最长上升子序列指的是序列中最长的单调递增的子序列。
如对于序列 \([2,5,3,4,1,7,6]\),它的最长上升子序列为 \([2,3,4,7]\) 和 \([2,3,4,6]\)。
1 2 3 4 5 6 7 8 9 10 11 12 |
|
记录一个额外的递增序列 栈 \(s\),如果当前元素 \(x\) 大于栈顶元素,直接将该元素 push
到栈中,否则,将栈中最近的一个大于等于 \(x\) 的元素替换为 \(x\)。经过这样的操作,不会对最长上升子序列有影响,而通过使用二分查找递增的序列,可以将时间复杂度降低到 \(\mathcal{O}(n\log(n))\)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|