給你一個(gè)整數(shù)數(shù)組 nums ，找到其中最長(zhǎng)嚴(yán)格遞增子序列的長(zhǎng)度。子序列是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數(shù)組 [0,3,1,6,2,2,7] 的子序列。示例 1：輸入：nums = [10,9,2,5,3,7,101,18] 輸出：4 解釋：最長(zhǎng)遞增子序列是 [2,3,7,101]，因此長(zhǎng)度為 4 。 示例 2：輸入：nums = [0,1,0,3,2,3] 輸出：4 示例 3：輸入：nums = [7,7,7,7,7,7,7] 輸出：1鏈接：https://leetcode-cn.com/problems/longest-increasing-subsequenceclass Solution:def lengthOfLIS(self, nums: List[int]) -> int:# 方法一# if not nums:return 0# dp = [1] * len(nums)# for i in range(len(nums)):# for j in range(i):# if nums[i] > nums[j]:# dp[i] = max(dp[i],dp[j] + 1)# return max(dp)# 方法二if not nums: return 0def findnumber(dp,i):l, r = 0, len(dp)-1while l < r:mid = (l+r)//2if dp[mid] == i:return midelif dp[mid] < i:l += 1else:r = midreturn ldp = [nums[0]]for i in range(1, len(nums)-1):if nums[i] > dp[-1]:dp.append(nums[i])else:idx = findnumber(dp, nums[i])dp[idx] = nums[i]if nums[-1] <= dp[-1]:return len(dp)else:return len(dp) + 1

總結(jié)

以上是生活随笔為你收集整理的Leetcode 300 最长递增子序列 (每日一题 20210803)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。