LeetCode.jpg
300. 最長(zhǎng)上升子序列
300. 最長(zhǎng)上升子序列
給定一個(gè)無(wú)序的整數(shù)數(shù)組径荔，找到其中最長(zhǎng)上升子序列的長(zhǎng)度。
示例:
輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長(zhǎng)的上升子序列是 [2,3,7,101]，它的長(zhǎng)度是 4。
說(shuō)明:
可能會(huì)有多種最長(zhǎng)上升子序列的組合，你只需要輸出對(duì)應(yīng)的長(zhǎng)度即可乾翔。
你算法的時(shí)間復(fù)雜度應(yīng)該為 O(n2) 。
進(jìn)階: 你能將算法的時(shí)間復(fù)雜度降低到 O(n log n) 嗎?
Python3 實(shí)現(xiàn)
動(dòng)態(tài)規(guī)劃
# @author:leacoder
# @des: 動(dòng)態(tài)規(guī)劃 最長(zhǎng)上升子序列 時(shí)間復(fù)雜度 O(n*n)
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums: return 0
result = 1
DP = [1 for i in range(len(nums))] # DP[ii] 表示 從 0 到 ii 且 第ii元素nums[ii]被選入最長(zhǎng)上升子序列 的 序列長(zhǎng)度 至少 為 1
for i in range(1,len(nums)):
for j in range(i):
if nums[j] < nums[i]: # 表示 序列為上升的 DP[j] 第j元素nums[j]被選入最長(zhǎng)上升子序列 的 序列長(zhǎng)度
DP[i] = max(DP[i],DP[j] + 1) # 這時(shí) nums[i] 被選入，長(zhǎng)度 + 1稳强。max 找出 第 0 到 i 元素 被選入最長(zhǎng)上升子序列 的 序列長(zhǎng)度 的 最大值
result = max(result,DP[i])
return result
維護(hù)子序列+二分查找
# @author:leacoder
# @des: 維護(hù)子序列+二分查找 最長(zhǎng)上升子序列 時(shí)間復(fù)雜度 O(n log n)
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
tails = [0] * len(nums)
size = 0 # 最長(zhǎng)上升子序列長(zhǎng)度
for num in nums:
i , j = 0 , size
while i != j: # 二分查找 num 插入位置
m = int((i + j)/2)
if tails[m] < num :
i = m + 1 # 查找后半段
else:
j = m # 查找前半段
# i 為數(shù)據(jù)插入位置 ，可能 1和悦、已有替換 2退疫、后面新增替換
tails[i] = num #
# 這之前 size 為 num 插入前 最長(zhǎng)上升子序列長(zhǎng)度
size = max(i+1,size) # 1、已有替換 size > i+1 2鸽素、后面新增替換 size < i+1
return size
GitHub鏈接：
https://github.com/lichangke/LeetCode
知乎個(gè)人首頁(yè)：
https://www.zhihu.com/people/lichangke/
簡(jiǎn)書(shū)個(gè)人首頁(yè)：
http://www.reibang.com/u/3e95c7555dc7
個(gè)人Blog:
https://lichangke.github.io/
歡迎大家來(lái)一起交流學(xué)習(xí)
