Python nlogn binary search 44ms solution


  • 4
    F
    class Solution(object):
    def lengthOfLIS(self, nums):
        if not nums: return 0
        c=[nums[0]]
        for i in nums:
            if i<=c[0]:
                c[0]=i
            elif i>c[-1]:
                c+=i,
            else:
                index=self.bs(c ,0, len(c), i)
                c[index]=min(i, c[index])
        return len(c)
        
    def bs(self, nums, l, r, key):
        while r-l>1:
            m=(r+l)/2
            if nums[m]>=key:
                r=m
            else:
                l=m
        return r

Log in to reply
 

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