首页 > 试题广场 >

最长上升子序列(三)

[编程题]最长上升子序列(三)

热度指数：75180 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围： $0 \le n \le 200000 , 0 \le arr_i \le 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

Draught

from collections import defaultdict, deque
import bisect
import math
import itertools

Yes, No = "Yes", "No"
YES, NO = "YES", "NO"
mod = int(1e9 + 7)

class Solution:
    def LIS(self, ls):
        n = len(ls)
        # 当前下标的最长长度
        len_ls = [0] * n
        # 构造数组
        inc_ls = []
        # 正常添加达到的长度
        seq_len = 0
        # 结果记录
        max_length = 0
        for i in range(len(ls)):
            cur = ls[i]
            j = bisect.bisect_left(inc_ls, cur)
            
            if j == len(inc_ls): # cur应该插入到最后面则append
                inc_ls.append(cur)
                seq_len += 1
                len_ls[i] = seq_len
            else:
                inc_ls[j] = cur
                len_ls[i] = j + 1 
            max_length = max(max_length, len_ls[i])
        
        # 构造结果 长度为max_length
        res = [0] * max_length
        for i in range(len(ls) - 1, -1, -1):
            if len_ls[i] == max_length:
                res[max_length - 1] = ls[i]
                max_length -= 1
        return res

编辑于 2024-03-03 11:49:20 回复(0)

Python

牛客840647990号

#
# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
#
class Solution:
def LIS(self , arr ):
# write code here
n = len(arr)
if n==0:
return []
res = [arr[0]]
maxLen = [0] * n
for i in range(1,n):
if arr[i] > res[-1]:
maxLen[i] = len(res)
res.append(arr[i])

else:
l = 0
r = len(res) - 1
while l <= r:
m = (r - l)//2 + l
if res[m]>= arr[i]:
r = m -1
else:
l= m + 1
res[l] = arr[i]
maxLen[i] = l
# 2
length = len(res)
lis = [0] * length
j = length - 1
# print(res)
# print(maxLen)
for i in range(n-1,-1,-1):
if j == maxLen[i]:
lis[j] = arr[i]
j -= 1
return lis

发表于 2021-07-12 20:20:38 回复(0)

Python

nlp_mon

f = []
    for i in range(len(nums)):
        if not f&nbs***bsp;nums[i] > f[-1]:
            f.append(nums[i])
        else:
            pos = bisect.bisect_left(f, nums[i])
            f[pos] = nums[i]
    return len(f)

发表于 2021-07-06 11:17:48 回复(0)

Python

Keosu

import bisect
class Solution:
    def LIS(self , arr ): 
        dp, m = [], [] 
        for i, x in enumerate(arr):
          if not m or x > m[-1]:
            m.append(x)
            dp.append(len(m))
          else:
            idx = bisect.bisect_left(m, x)
            m[idx] = x  
            dp.append(idx + 1)
        cur = len(m) - 1
        ans = [0] * len(m)
        for i, x in enumerate(reversed(dp)):
            if x == cur + 1:
              ans[cur] = arr[-i-1]
              cur -= 1
        return ans

编辑于 2021-07-05 21:58:58 回复(0)

Python

牛客804608857号

# 简单又无脑的方法

class Solution:

def LIS(self , arr ):
self.arr = arr
arr.remove(2)
arr.remove(5)
arr.remove(6)
arr.remove(7)
arr.sort()
return arr

发表于 2021-06-09 23:11:38 回复(1)

Python

XingyuXiong

按照楼上java答案同样思路写了一个python的，nlogn的贪心+二分，题目给的自测输入答案是对的，但是保存并提交会超时。。

#
# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
#
class Solution:
    def LIS(self , arr ):
        # write code here
        res=[]
        maxlen=[]
        if not arr:
            return res
        res.append(arr[0])
        maxlen.append(1)
        for i in range(1,len(arr)):
            if arr[i]>res[-1]:
                res.append(arr[i])
                maxlen.append(len(res))
            else:
                last=len(res)-1
                first=0
                mid=(last+first)/2
                pos=-1
                while res[mid]!=arr[i]:
                    mid=(last+first)/2
                    if res[mid]==arr[i]:
                        pos=mid
                        break
                    elif first<=last and res[mid]>arr[i]:
                        if mid==0&nbs***bsp;res[mid-1]<=arr[i]:
                            pos=mid
                            break
                        else:
                            last=mid-1
                    else:
                        first=mid+1
                if pos!=-1:
                    res[pos]=arr[i]
                    maxlen.append(pos+1)
        j=len(res)
        i=len(arr)-1
        while j>0:
            if maxlen[i]==j:                
                j-=1
                res[j]=arr[i]
            i-=1
        return res

发表于 2021-05-01 23:16:00 回复(0)

Python

猫牛

leecode的官方答案，居然通不过。。。。

class Solution:
    def LIS(self , nums ):
        d = []
        for n in nums:
            if not d or n > d[-1]:
                d.append(n)
            else:
                l, r = 0, len(d) - 1
                loc = r
                while l <= r:
                    mid = (l + r) // 2
                    if d[mid] >= n:
                        loc = mid
                        r = mid - 1
                    else:
                        l = mid + 1
                d[loc] = n
        return d

编辑于 2021-04-20 01:11:02 回复(0)

Python

胡桃你带我走吧

垃圾牛客网，python直接返回nums都超时

发表于 2021-04-19 17:10:26 回复(0)

Python

牛客145300716号

# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
class Solution:
def LIS(self , arr ):
# write code here
n = len(arr)
list = [1]*n
for i in range(1,n):
for j in range(0,i):
if arr[i] > arr[j]:
list[i] = max(list[j]+1,list[i])

var = max(list)
value = []
for i in range(0,n):
if var == list[n-1-i]:
value.append(arr[n-1-i])
var -= 1

return value[::-1]

超时

发表于 2021-04-14 01:47:58 回复(0)

Python

杨辉^牛年大吉

动态规划方法：

提交后会超时，但结果正确

class Solution:

def LIS(self , arr ):
# write code here
if not arr:return []
n = len(arr)
dp = [1]*n
ret = []
maxLen = 0
for i in range(1, n):
for j in range(i):
if arr[i]>arr[j]:
dp[i]=dp[j]+1

ret = []

maxLen = max(maxLen, dp[i])

for i in range(n-1,-1,-1):
if dp[i]==maxLen:
maxLen-=1
ret.append(arr[i])
return ret[::-1]

编辑于 2021-02-28 18:36:54 回复(0)

Python

字节校招内推官

python 会超时，但这个代码是对的

class Solution:
    def LIS(self, arr):
        n = len(arr)
        m = [0] * n
        for x in range(n - 2, -1, -1):
            for y in range(n - 1, x, -1):
                if arr[x] < arr[y] and m[x] <= m[y]:
                    m[x] += 1
            max_value = max(m)
            result = []
            for i in range(n):
                if m[i] == max_value:
                    result.append(arr[i])
                    max_value -= 1
        return result

发表于 2020-12-30 17:23:56 回复(0)

Python

PPHT

python3有bug，直接返回数组都会显示超时。。。

class Solution:
    def LIS(self, arr):
        # write code here
        return arr

发表于 2020-12-04 12:26:15 回复(9)

Python

pyxiea

参考kite97大佬的代码，python实现：

#
# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
#
class Solution:
    def LIS(self, arr):
        if arr is None or len(arr) == 0:
            return []
        res = [arr[0]]
        temp = [1]  # 每个位置为终点的LIS长度
        for i in range(1, len(arr)):
            if arr[i] > res[-1]:
                res.append(arr[i])
                temp.append(len(res))
            else:
                low, high = 0, len(res)
                while low < high:
                    mid = (high - low) // 2 + low
                    if res[mid] >= arr[i]:
                        high = mid
                    else:
                        low = mid + 1
                res[low] = arr[i]
                temp.append(low + 1)
        i = len(arr) - 1
        k = len(res) - 1
        while k >= 0:
            if temp[i] - 1 == k:
                res[k] = arr[i]
                k -= 1
            i -= 1
        return res

发表于 2020-09-10 21:30:26 回复(0)