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

最长上升子序列(三)

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

全部评论

相关推荐

uu们,拒offer时hr很生气怎么办我哭死
爱睡觉的冰箱哥:人家回收你的offer,或者oc后没给你发offer的时候可不会愧疚你,所以你拒了也没必要愧疚他。
点赞 评论 收藏
分享
06-08 22:25
门头沟学院 Java
从零开始的转码生活:这hr不会打开手机不分青红皂白给所有人群发这句话,过一会再给所有人再发一遍,这肯定会有重复的,不管,再过一会再发一遍
点赞 评论 收藏
分享
06-25 09:33
厦门大学 Java
程序员饺子:现在日常估计没啥hc了,等到八月多估计就慢慢有了。双九✌🏻不用焦虑的
投递快手等公司7个岗位
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-03 17:37
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

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