Python O(nlogn) beats 79.82%


  • 0
    class Solution(object):
        def lengthOfLIS(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if not nums:
                return 0
            stack = [nums[0]]
            maxLen = 1
            for i in range(1, len(nums)):
                if nums[i] > stack[-1]:
                    stack.append(nums[i])
                else:
                    index = self.binarySearch(stack, nums[i])
                    stack[index] = nums[i]
                maxLen = max(maxLen, len(stack))
            return maxLen
        
        def binarySearch(self, stack, num):
            left, right = 0, len(stack)-1
            while left < right:
                mid = left + (right - left) / 2
                if stack[mid] >= num:
                    right = mid
                else:
                    left = mid + 1
            return left
    

Log in to reply
 

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