NC91 最长上升子序列(三)

序列(三)"/>

NC91 最长上升子序列(三)

描述

给定数组 arr ，设长度为 n ，输出 arr 的最长上升子序列。（如果有多个答案，请输出其中 按数值(注：区别于按单个字符的ASCII码值)进行比较的 字典序最小的那个）

数据范围：10000000000≤n≤200000,0≤arri​≤1000000000

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

示例1

输入：

[2,1,5,3,6,4,8,9,7]

返回值：

[1,3,4,8,9]

示例2

输入：

[1,2,8,6,4]

返回值：

[1,2,4]

说明：

其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个 按数值进行比较的字典序 最小，故答案为（1，2，4）

解题思路：

贪心 + 二分查找

题解 | #最长递增子序列#_牛客博客

Python代码：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
#
class Solution:def search(self, nums, target):i, j = -1, len(nums)while i + 1 < j:mid = i + (j - i) // 2if nums[mid] < target:i = midelse:j = midreturn jdef LIS(self , arr: List[int]) -> List[int]:# write code hereres = []max_length = []n = len(arr)for num in arr:if not res or num > res[-1]:res.append(num)max_length.append(len(res))else:loc = self.search(res, num)res[loc] = nummax_length.append(loc + 1)maxlen = len(res) for i in range(n - 1, -1, -1):if maxlen == max_length[i]:res[maxlen - 1] = arr[i]maxlen -= 1return res