奇怪的 Leetcode Memory Limit Exceeded 错误

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

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

@jedihy 谢谢回复。

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

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

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

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

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

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

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

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