Python O(nlogn)


  • 1
    H
    class Solution(object):
        def find(self,res,end,x):
            l = 0
            r = end
            while l<r:
                mi = (l+r)/2
                if res[mi] == x: return mi
                if res[mi]>x:
                    r = mi
                else:
                    l = mi+1
            return r
    
        def lengthOfLIS(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            res = []
            for i in nums:
                l = len(res)
                index = self.find(res,l,i)
                if index==l:
                    res.append(i)
                else:
                    res[index]=i
            return len(res)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.