最长上升子序列(三)

问题简述

给定数组，返回字典序最小的最长上升子序列；

最长上升子序列(三)_牛客题霸_牛客网

思路：动态规划

• 为了返回字典序最小的 LIS，本题需要结合两种 dp 状态；

  • 记 dp_min[i] 表示长度为 (i+1) 的 LIS 结尾的最小值；

  • 记 dp_len[i] 表示以 arr[i] 结尾的 LIS 的长度；

  这两种状态都可以用来求 LIS 的长度，前者的时间复杂度为 $O(n\log n)$，后者为 $O(n^2)$

• 得到这两个状态序列后就可以来计算具体的 LIS 了；下面举例说明如何使用这两个状态来还原 LIS；

  arr:    [1,2,8,6,4]
  dp_len: [1,2,3,3,3]
  dp_min: [1,2,4]
  # 这里省略了这两个状态序列的生成过程，
  # 因为 dp_len 可以在计算 dp_min 的过程中一起获得，因此时间复杂度依然是 `O(NlogN)`
  
  初始化：
      cnt = len(dp_min) # LIS 的长度
      ret = [0] * cnt  # 记录 LIS
  
  然后逆序遍历 dp_len
  当 dp_len[i] == cnt 时，将 ret[cnt - 1] 赋值为 arr[i]，同时 cnt -= 1
  
  为什么要逆序遍历？
      举个例子，arr 结尾的三个数，其最大的 LIS 长度都是 3，但其中 4 是最小的，
      因为如果它不是最小的，意味着它对应的 LIS 长度就应该大于 3 了

Python：递归写法

class Solution:
    def LIS(self, arr: List[int]) -> List[int]:
        if not arr: return []
        
        import sys
        from bisect import bisect_left
        sys.setrecursionlimit(1000000)
        
        dp_min = []  # dp_min[i] 表示长度为 (i+1) 的 LIS 结尾的最小值
        dp_len = []  # dp_len[i] 表示以 arr[i] 结尾的 LIS 的长度

        def dfs(i):
            if i == 0:
                dp_min.append(arr[0])
                dp_len.append(1)
                return 
            
            dfs(i - 1)
            
            if arr[i] > dp_min[-1]:
                dp_min.append(arr[i])
                dp_len.append(len(dp_min))
            else:
                idx = bisect_left(dp_min, arr[i])
                dp_min[idx] = arr[i]
                dp_len.append(idx + 1)  # 这里直接使用索引作为长度，如果没有 dp_min，就需要顺序遍历，这也是 dp_len 时间复杂度高的原因
        
        N = len(arr)
        dfs(N - 1)
        
        cnt = len(dp_min)
        ret = [0] * cnt
        for i in range(len(arr) - 1, -1, -1):
            if dp_len[i] == cnt:
                cnt -= 1
                ret[cnt] = arr[i]
        
        return ret

Python：迭代写法（推荐）

class Solution:
    def LIS(self, arr: List[int]) -> List[int]:
        if not arr: return []
        
        from bisect import bisect_left
        
        dp_min = [arr[0]]  # dp_min[i] 表示长度为 (i+1) 的 LIS 结尾的最小值
        dp_len = [1]  # dp_len[i] 表示以 arr[i] 结尾的 LIS 的长度

        N = len(arr)
        for i in range(1, N):
            if arr[i] > dp_min[-1]:
                dp_min.append(arr[i])
                dp_len.append(len(dp_min))
            else:
                idx = bisect_left(dp_min, arr[i])
                dp_min[idx] = arr[i]
                dp_len.append(idx + 1)  # 这里直接使用索引作为长度，如果没有 dp_min，就需要顺序遍历，这也是 dp_len 时间复杂度高的原因
        
        cnt = len(dp_min)
        ret = [0] * cnt
        for i in range(len(arr) - 1, -1, -1):
            if dp_len[i] == cnt:
                cnt -= 1
                ret[cnt] = arr[i]
        
        return ret