300 Longest Increasing Subsequence

找出数组中最大的增长数量

 

my solution (8ms, 66.89%)

emm... 考虑将每一个下降的 slice 视为一个数组, 因为这些数组只可能产生一个值

而再将这些 slice 循环, 每次从当前节点选择最小的数字, 每次前进时选择一个最小的比上一个节点大的数字

然后计数, 一次遍历下来就得到了最大增长序列的长度

复杂度是一次 O(n) 的遍历 + 切片之后数组长度的遍历, 接近 O(n2)

emm... 代码有点长

8ms 那个是我做的, 0 不是

 

best solution

简单来说就是通过不断将数组按照升序添加到 slice 里面 (我将其称作 slice, 因为它的行为不太像 stack)

slice 的元素只有两种情况会变更:

要么有更小的元素覆盖, 要么比 slice 中所有元素都大, 然后 append

因为题目要求的只要长度, 所以即使 slice 里面元素可能是错误的, 也没关系, 长度是对的

这样的复杂度是 O(n), 其实原理还是挺容易理解的, 为什么我就没想到呢 = =