leetcode300-- Longest increasing Subsequence.(LIS)(注意O(nlogn)解法)

leetcode300-- Longest increasing Subsequence.(LIS)(注意O(nlogn)解法)

题目


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?


###

想法是用DP, 即用dp[i]来代表以nums[i]为结尾的最长递增子序列,显然它不小于1(1的时候是只有它自已),所以这样定义是有意义的。 然后再从1到i看起,因为这时候的子序列如果还有其他的元素的话,结尾一定是在前面,而且这个元素没有nums[i]大,所以dp[i],应该是遍历这些以后的最大值,

dp[i] = max(dp[i], dp[j]+1), 其中j<i并且nums[j]<nums[i].

如何理解上面的式子,右边的dp[i]不是不知道吗?

其实dp[i]都是初始化为1的.所以这个式子是可以的。

最终代码如下

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

也可以用 nlogn 的想法, 先说这个想法, 这个想法就像人从头到尾去找一样,比如 [10,9,2,5,3,7,101,18], 这样一个数组, 先把10拿在手里, 然后去看下一个,发现9更小,就把这经换成9, 继续往前发现2更小,就把2换了,然后发现5,比2大,就把5也放进来, 所以现在变成了[2,5], 然后再看3, 发现3比2大,比5小,所以就找3在这里面的位置,发现应该把5换掉, 所以就变成了[2,3], 然后是发现7比3要大,所以变成了[2,3,7], 然后发现101 比7大,所以变成了[2,3,7,101], 最后发现18比2大,比101小,所以它肯定比里面的某个元素小, 然后找到了时候发现是101, 所以它应该和101换一下,最终得到的数组就是[2,3,7,18], 所以要输出的数字就是4。 我们会发现,最长递增子序列是不唯一的. 但是最后要输出的长度是对的.

所以有了上面的介绍,思路也就清晰了,即维护一个单调递增的数组A, 如果发现当前的元素比这个A中的元素还要小,就将A中的换掉,如果发现比A中的所有的都要大,就把它append起来, 如果在中间的话,就替换掉它应该换掉的那个元素.具体有三种情况,1. 当前的这个元素比A中的最小的还要小,就直接换A最左边的那个元素,2.当前的这个元素比A的最右边的还要大,这时候就把A变长,3. 发现当前的这个元素可以在A的里面的某个位置,这时候用二分查找找到其应该在的位置. 然后将A中的那个元素换成当前的这个元素.

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        if len(nums)==0:
            return 0    
        ends = [nums[0]]
        
        for i in range(len(nums)):
            # 看当前的元素,
            # 如果比ends的首元素小,就换掉
            if (nums[i]<ends[0]):
                ends[0] = nums[i]
            # 如果比最后一个元素大的话,就放到最后
            elif nums[i]> ends[-1]:
                ends.append(nums[i])
            # 如果是在首元素和尾元素之间的话,
            else:
                left = 0
                right = len(ends)
                # 二分查找找到其应该在的位置
                while(left<right):
                    mid = left +(right-left)/2
                    if(ends[mid]<nums[i]):
                        left = mid+1  # 注意是加1.
                    else:
                        right = mid
                ends[right] = nums[i]    
        return len(ends)
        

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦