题解 | #最长递增子序列#

最长递增子序列

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

python使用bisect和patient sort, 借助pre记录每个位置的前驱

import bisect
class Solution:
    def LIS(self , arr ):
        stack = [0]
        pre = [-1] * len(arr)

        class Range:
            def __getitem__(self, i):
                return arr[stack[i]]
            def __len__(self):
                return len(stack)

        for i in range(1, len(arr)):
            idx = bisect.bisect_left(Range(), arr[i])
            if idx < len(stack):
                stack[idx] = i
                pre[i] = stack[idx - 1] if idx - 1 >=0 else -1
            else:
                pre[i] = stack[-1]        
                stack.append(i)

        cur = stack[-1]
        res = []
        while cur != -1:
            res.append(arr[cur])
            cur = pre[cur]
        return res[::-1]
全部评论

相关推荐

SinyWu:七院电话面的时候问我有没有女朋友,一听异地说你赶紧分。我:???
点赞 评论 收藏
分享
11-08 13:58
门头沟学院 Java
程序员小白条:竟然是蓝桥杯人才doge,还要花钱申领的offer,这么好的公司哪里去找
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务