常规的 DP 题，最长单调递增子序列：
https://leetcode.com/problems/longest-increasing-subsequence/
我的代码：
提交后，最后一个很长的 case 会报 Memory Limit Exceeded 错误。
但是很奇怪，我加了 remove duplicate 的代码还是会有这个错误。
另外，这个代码并不只是输出长度，所以并不是最简，不要纠结于此，但是 O(nlog(n)) 的时间复杂度。
那个 remove duplicate 的代码比较傻，但也不至于 Memory Limit Exceeded。
我试过另一种方法 remove duplicate，也是一样。
 |
1
jedihy Mar 8, 2017
因为你的空间复杂度是 O(N^2)，而实际上可以做到 O(n)，因为你需要得到长度而不是子序列，所以只记录最后一个元素。另外推荐这样的地方用 upper_bound 而不是直接写个二分容易错，代码看起来也不太舒服。
下面是我自己写的 python 的，给你参考下 class Solution(object): def lengthOfLIS(self, nums): """ :type nums: List[int] :rtype: int """ tail = [] for i in xrange(0, len(nums)): idx = bisect.bisect_right(tail, nums[i]) if idx - 1 >= 0 and nums[i] == tail[idx - 1]: continue if idx == len(tail): tail.append(nums[i]) else: tail[idx] = nums[i] return len(tail) |
|
3
jedihy Mar 8, 2017
其次， nlogn 已经够快了，去重那一步没什么必要吧
|
 |
4
lsmgeb89 OP @jedihy 谢谢回复。
昨天由于没人回，自己也找了 O(n) 的版本。 只吐槽一点，我估计 LeetCode 算的是所有 cases 加起来用的空间来判断的我触发 memory limit 了。 但那个界面给人的感觉是只有那一个 case 超了 memory limit 。 然后我就很 confused ，因为加了去重，即使是 O(n^2)，就那一个 case 来说，实际用的空间也很小。 去重是为了是减少一点空间，如果用了 O(n) 的版本，确实多余。 |
|
5
lsmgeb89 OP 由于在做 CLRS 15.4-6 ，所以要输出序列的版本，而不只是长度。在这个条件下， O(n) 不是太容易想到。 LeetCode 只是借着用来测试下代码的正确性。
|
|
6
jedihy Mar 9, 2017 via iPhone
对，都是累积的，单个去算这个系统就太难设计了
|
|
7
jedihy Mar 9, 2017 via iPhone
我觉得这个 nlogn 的方法是自己想不出来的，我是在很久之前 geeksforgeeks 上看的
|
Select Language