LeetCode 300. Longest Increasing Subsequence 题解

LeetCode 300. Longest Increasing Subsequence 题解题目描述给你一个整数数组nums找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。示例 1输入nums [10,9,2,5,3,7,101,18] 输出4 解释最长递增子序列是 [2,3,7,101]因此长度为 4 。示例 2输入nums [0,1,0,3,2,3] 输出4示例 3输入nums [7,7,7,7,7,7,7] 输出1解题思路方法一动态规划思路定义dp[i]为以nums[i]结尾的最长递增子序列的长度状态转移方程dp[i] max(dp[j] 1) for j in 0..i-1 if nums[j] nums[i]初始化dp[i] 1因为每个元素自身构成一个长度为 1 的子序列最终结果为max(dp)复杂度分析时间复杂度O(n²)其中 n 是数组的长度。需要双重循环遍历数组。空间复杂度O(n)需要一个长度为 n 的数组来存储状态。方法二贪心算法 二分查找思路维护一个数组tails其中tails[i]表示长度为i1的递增子序列的最小末尾元素遍历数组中的每个元素如果当前元素大于tails的最后一个元素将其添加到tails末尾否则使用二分查找找到tails中第一个大于等于当前元素的位置并用当前元素替换它最终tails的长度即为最长递增子序列的长度复杂度分析时间复杂度O(n log n)其中 n 是数组的长度。遍历数组需要 O(n) 的时间每次二分查找需要 O(log n) 的时间。空间复杂度O(n)需要一个数组来存储tails。代码实现方法一动态规划class Solution: def lengthOfLIS(self, nums: List[int]) - int: n len(nums) if n 0: return 0 dp [1] * n for i in range(1, n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)方法二贪心算法 二分查找class Solution: def lengthOfLIS(self, nums: List[int]) - int: tails [] for num in nums: # 二分查找找到第一个大于等于 num 的位置 left, right 0, len(tails) while left right: mid (left right) // 2 if tails[mid] num: left mid 1 else: right mid # 如果找到的位置等于 tails 的长度说明 num 比所有元素都大添加到末尾 if left len(tails): tails.append(num) # 否则用 num 替换该位置的元素 else: tails[left] num return len(tails)测试用例测试用例 1输入nums [10,9,2,5,3,7,101,18]输出4测试用例 2输入nums [0,1,0,3,2,3]输出4测试用例 3输入nums [7,7,7,7,7,7,7]输出1测试用例 4输入nums []输出0总结本题是动态规划的经典问题主要考察对状态定义和状态转移方程的理解。两种方法各有特点动态规划代码简洁易懂逻辑清晰但时间复杂度较高适用于小规模数据。贪心算法 二分查找时间复杂度较低适用于大规模数据但理解起来相对复杂。在实际应用中对于一般规模的数组两种方法都可以使用。但对于大规模数组贪心算法 二分查找的方法更为高效。无论使用哪种方法核心思想都是找到最长的严格递增子序列这对于解决许多实际问题都有帮助例如最长递增子序列的应用包括最长递增子串、最长递减子序列、最长不下降子序列等。