最长递增子序列

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(n log(n)) 吗?

思路：

动态规划：

遇到子序列，子数组，子串问题的第一个思路就是，从左到右遍历。

假设数组为[1,3,2,4,6,7]其中最长递增子序列为[1,2,4,6,7]当遍历到4时我们需要得到前面数组的信息，比如j=2,如果nums[3]>nums[2],以3结尾的数组的最长子序列要加一

按照动态规划五部曲

第一步定义dp数组含义

• dp[i]的值代表nums以num**s[i]结尾的最长子序列长度
• 初始化参数，每个数都可以是子数组长度为1的最长子序列，所以初始化为1
• 确定遍历顺序：前面说了从左到右
• 递归方程：num[i]>num[j],dp[i] = max(dp[j] + 1, dp[i])
• 打印dp数组

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

二分法：

由于获取到j要遍历0-i之间的所有数，所以可以省略这一步吗。

答案是可以的，定义一个数组来接住递增数组的每一个元素就可以了。

定义个tail 数组，用于保存当前找到的LIS中的最小可能尾部值，保证这个数组是连续递增的

bisect_left 函数用来查找 nums[i] 在 tail 中应插入的位置，从而保证 tail 数组始终是有序的。

如果 nums[i] 大于 tail 数组中的所有元素，则它将扩展当前的LIS；否则，它会替换掉 tail 中比它大的第一个元素，这样可以确保后续的数字有更小的目标去匹配，有助于形成更长的递增子序列。

import bisect

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # 初始化一个长度与nums相同，但是所有元素都是正无穷大的列表。
        tail = [float('inf')] * len(nums)
        ans = 0
        
        for i in range(len(nums)):
            # 使用二分查找找到nums[i]在tail中的位置
            index = bisect.bisect_left(tail, nums[i])
            
            # 更新该位置的值为nums[i]
            tail[index] = nums[i]
        
        # 计算tail中实际包含的有效元素数量（即不为正无穷大的元素数量）
        for num in tail:
            if num != float('inf'):
                ans += 1
            else:
                break
        
        return ans

673. 最长递增子序列的个数

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。

示例 1:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:

输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

提示:

• 1 <= nums.length <= 2000
• -106 <= nums[i] <= 106

思路：

dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度，count[i] 表示这些子序列的数量。

• 当 dp[j] + 1 > dp[i] 时，这意味着通过将 nums[i] 添加到以 nums[j] 结尾的递增子序列中，可以获得一个比当前以 nums[i] 结尾的最长递增子序列还要长的新序列。因此，你需要更新 dp[i] 为 dp[j] + 1，同时将 count[i] 更新为 count[j]，因为现在 nums[i] 的最长递增子序列数量与 nums[j] 的相同。
• 当 dp[j] + 1 == dp[i] 时，这表示可以通过添加 nums[i] 到以 nums[j] 结尾的递增子序列来获得与当前以 nums[i] 结尾的最长递增子序列一样长的新序列。这意味着存在多条路径到达相同的最长递增子序列长度。因此，你需要将 count[j] 加到 count[i] 上，以累计所有可能的路径数。

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        count = [1] * len(nums)
        dp = [1] * len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    if dp[i] < dp[j] + 1:
                        dp[i] = max(dp[i], dp[j] + 1)
                        count[i] = count[j]
                    elif dp[j] + 1 == dp[i]:
                        count[i] += count[j]
        max_size = max(dp)
        ans = 0
        for i in range(len(nums)):
            if dp[i] == max_size:
                ans += count[i]
        return ans

354. 俄罗斯套娃信封问题

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。

示例 1：

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

示例 2：

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

提示：

• 1 <= envelopes.length <= 105
• envelopes[i].length == 2
• 1 <= wi, hi <= 105

思路：

和上题连续递增子序列完全一致，当时我在做就是在纠结信封的宽度一致如何处理，其实只需要将高度递减就可以避免同宽的情况了，因为它先被选中了，后续的就不会被再次选中了

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        # 降序保证在同宽里高是最大的, 先被选择
        envelopes = sorted(envelopes, key=lambda obj: (obj[0] , -obj[1]))
        tails = [float('inf')] * len(envelopes)
        for i in range(len(envelopes)):
            index = bisect.bisect_left(tails, envelopes[i][-1])
            tails[index] = envelopes[i][-1]

        ans = 0
        for temp in tails:
            if temp == float('inf'):
                break
            else:
                ans += 1
        return ans