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

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]