300. 最长递增子序列

给你一个整数数组 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

提示：

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

进阶：

• 你可以设计时间复杂度为 O(n2) 的解决方案吗？
• 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

二分查找 动态规划 中等

思路

1. 动态规划
2. 贪心

代码

1. 动态规划

   class Solution:
       def lengthOfLIS(self, nums: List[int]) -> int:
           if not nums:
               return 0
           dp = []
           for i in range(len(nums)):
               dp.append(1)
               for j in range(i):
                   if nums[i] > nums[j]:
                       dp[i] = max(dp[i], dp[j] + 1)
           return max(dp)
   

2. 贪心

   '''
   新增的数只要比前一位大（也就是d的最后一位）,那就说明这个数字可以起到延长序列的作用，所以append上；
   否则，如果新增的数比前一位小（严格增的话，这里包含等于），那就说明这个数字直接拼上前一位元素，不能起到延长序列的作用（构不成严格增序列）， 
   又因为d中存的是每一个长度末尾最小的元素，且d中现存的元素都是在nums[i]之前出现过的，因此找到nums[i]在d上的位置，并不会影响子序列的顺序。 
   nums[i]要是比d中所有值都小，那说明这个数只能打头，所以就放到第一位； 
   如果nums[i]在d中的位置在第2位，那说明第一位曾经出现过的数字可以和该数字构成一个长度为2的子序列 
   只不过由于贪心的思想，不得不找更小的末尾元素在适合的长度上。 
   如果还理解不了，需要记住，无论是d中现有的数字还是被替换掉的数字，在nums中的顺序都在nums[i]之前，因此只需要判断大小即可，位置是没有变的 
   或者可以这样理解：d的长度就是最长序列的长度
   '''
   class Solution:
       def lengthOfLIS(self, nums: List[int]) -> int:
           q = []
           for x in nums:
               i = bisect_left(q, x)
               q[i:i+1] = x,
           return len(q)