奇怪的 Leetcode Memory Limit Exceeded 错误

[lsmgeb89]

常规的 DP 题，最长单调递增子序列：

https://leetcode.com/problems/longest-increasing-subsequence/

我的代码：

https://github.com/lsmgeb89/leetcode_solution/blob/master/medium/300-longest-increasing-subsequence-2.h

提交后，最后一个很长的 case 会报 Memory Limit Exceeded 错误。

但是很奇怪，我加了 remove duplicate 的代码还是会有这个错误。

另外，这个代码并不只是输出长度，所以并不是最简，不要纠结于此，但是 O(nlog(n)) 的时间复杂度。

那个 remove duplicate 的代码比较傻，但也不至于 Memory Limit Exceeded。

我试过另一种方法 remove duplicate，也是一样。

[jedihy]

因为你的空间复杂度是 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)

[jedihy]

https://gist.github.com/csujedihy/07d8c7fc917fedff618a0f9774c0b45f

[jedihy]

其次， nlogn 已经够快了，去重那一步没什么必要吧

[lsmgeb89]

@jedihy 谢谢回复。

昨天由于没人回，自己也找了 O(n) 的版本。

只吐槽一点，我估计 LeetCode 算的是所有 cases 加起来用的空间来判断的我触发 memory limit 了。

但那个界面给人的感觉是只有那一个 case 超了 memory limit 。

然后我就很 confused ，因为加了去重，即使是 O(n^2)，就那一个 case 来说，实际用的空间也很小。

去重是为了是减少一点空间，如果用了 O(n) 的版本，确实多余。

[lsmgeb89]

由于在做 CLRS 15.4-6 ，所以要输出序列的版本，而不只是长度。在这个条件下， O(n) 不是太容易想到。 LeetCode 只是借着用来测试下代码的正确性。

[jedihy]

对，都是累积的，单个去算这个系统就太难设计了

[jedihy]

我觉得这个 nlogn 的方法是自己想不出来的，我是在很久之前 geeksforgeeks 上看的