序列(三)"/>
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
更多推荐
NC91 最长上升子序列(三)
发布评论