[LeetCode] 0300. 最長の増加サブシーケンス

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

中くらい

整数配列が与えられた場合 数字、戻る最長のものの長さ 厳密に増加する 後続.

例 1:

入力： 数値 = [10,9,2,5,3,7,101,18]
出力： 4
説明： 最も長く増加する部分列は [2,3,7,101] であるため、長さは 4 です。

例 2:

入力： 数値 = [0,1,0,3,2,3]
出力： 4

例 3:

入力： 数値 = [7,7,7,7,7,7,7]
出力： 1

制約:

1 <= nums.length <= 2500
-10 ⁴ <= nums[i] <= 10 ⁴

フォローアップ： で実行されるアルゴリズムを思いつきませんか O(n log(n)) 時間の複雑さ?

パイソン

				
					# 時間計算量: O(n^2) # 空間計算量: import List クラスの入力による O(1) 解決策: def lengthOfLIS(self, nums: List[int]) -> int: countList = [1] * len(nums ) range(1, len(nums)) の i の場合: range(i) の j の場合: nums[i] > nums[j] の場合: countList[i] = max(countList[i], countList[j] + 1) max(countList) を返します nums = [0, 1, 0, 3, 2, 3] print(Solution().lengthOfLIS(nums))

中くらい

パイソン

関連記事