O(NlogN) binary search solution


  • 0
    S

    last[i] means the minimum of last element of the i-length increasing sequence, since last is a increasing array, it can be updated by binary search .

    class Solution(object):
        def lengthOfLIS(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            last=[]
            for i in nums:
                left,right=0,len(last)-1
                while left<=right:
                    mid=(left+right)>>1
                    if last[mid]<i:
                        left=mid+1
                    else:
                        right=mid-1
                if left<len(last):
                    last[left]=i
                else:
                    last.append(i)
            return len(last)
    

Log in to reply
 

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