300._longest_increasing_subsequence.md

300. Longest Increasing Subsequence

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/longest-increasing-subsequence/description/

内容描述

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 
Note:

There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?

解题方案

思路 1

典型DP

递推关系式：

对于以num[i]结束的longest increasing subsequence的长度

dp[i] = dp[j] + 1 if num[i] > num[j] else dp[i], which 0 <= j < i

loop一圈，求出最长的

AC 代码, 时间复杂度为O(n^2)

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums or len(nums) == 0:
            return 0
        dp = [1] * len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[j]+1, dp[i])
        return max(dp)

Follow up

Could you improve it to O(n log n) time complexity?

思路 1

参考这篇🐂p的博客：

自己写二分

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def binarySearch(nums, l, r, key):
            while l < r-1:
                mid = l + (r - l)//2
                if (nums[mid] >= key):
                    r = mid
                else:
                    l = mid
            return r
        
        if not nums or len(nums) == 0:
            return 0

        tails = [0 for i in range(len(nums)+1)]
        tails[0] = nums[0]
        # always points empty slot
        length = 1
        for i in range(1, len(nums)):
            if (nums[i] < tails[0]):
                # new smallest value
                tails[0] = nums[i]
            elif (nums[i] > tails[length-1]):
                # A[i] wants to extend
                # largest subsequence
                tails[length] = nums[i]
                length+=1
            else:
                # A[i] wants to be current
                # end candidate of an existing
                # subsequence. It will replace
                # ceil value in tailTable
                tails[binarySearch(tails, -1, length-1, nums[i])] = nums[i]

        return length

思路 2

调用自带的二分

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums or len(nums) == 0:
            return 0
        
        lis = [nums[0]]
        for i in range(1, len(nums)):
            if nums[i] > lis[-1]:
                lis.append(nums[i])
            else:
                # 要用bisect_left，因为如果插入到右边就相当于多append了一个，而不再是replace了
                lis[bisect.bisect_left(lis, nums[i])] = nums[i]
        
        return len(lis)