题解 | #最长上升子序列(三)#

最长上升子序列(三)

http://www.nowcoder.com/practice/9cf027bf54714ad889d4f30ff0ae5481

#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
#
class Solution:
    def LIS(self , arr: List[int]) -> List[int]:
        # write code here
        b = [arr[0]]
        def binary_find(target):
            l, r = 0, len(b) - 1
            while l <= r:
                mid = (l + r) // 2
                if target > b[mid]:
                    l = mid + 1
                else:
                    r = mid - 1
            return l
        
        maxlen = [1]
        for i in arr[1:]:
            if i > b[-1]:
                b.append(i)
                maxlen.append(len(b))
            else:
                idx = binary_find(i)
                b[idx] = i
                maxlen.append(len(b[:idx + 1]))

        length=len(b)
        for i in range(len(arr)-1,-1,-1):
            if maxlen[i]==length:
                b[length-1]=arr[i]
                length-=1
        return b

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-08 10:39
一个证都没&nbsp;我能填什么
程序员小白条:别人有,你为什么没有,还是这个道理,社会就是比较,竞争,淘汰,你要安逸,那么就要做好淘汰的准备
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务