最长递增子序列

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        # 滑动窗口
        n = len(nums)
        if n <= 1: return n
        l, r, res = 0, 1, 1
        while r < n:
            while r < n and nums[r-1] < nums[r]: r += 1  
            res = max(res, r-l)
            l, r = r, r+1
        return res

复杂度

时间复杂度：$O(n)$
空间复杂度：$O(1)$

300. 最长递增子序列

https://leetcode-cn.com/problems/longest-increasing-subsequence/

题目描述

Note

给你一个整数数组 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$
$-10^4 <= nums[i] <= 10^4$

进阶：

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

思路

代码

Python 暴力解

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        动态规划 -- 暴力解
        n = len(nums)
        dp = [1]*n
        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp)

Python 动态规划 + 二分

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # 动态规划 + 二分
        # 二分： 寻找最左满足条件的索引
        def binary_search(nums, target):
            i, j = 0, len(nums)-1
            while i < j:
                mid = i + (j-i)//2
                if nums[mid] < target:
                    i = mid+1
                else:
                    j = mid
            return i
        # 遍历数组，生成最长单调数组 dp
        n, dp = len(nums), []
        for num in nums:
            if not dp or dp[-1] < num:
                dp.append(num)
                continue
            idx = binary_search(dp, num)
            dp[idx] = num
        return len(dp)

复杂度

时间复杂度：
- 暴力解: $O(n^2)$
- 动态规划: $O(nlogN)$
空间复杂度：$O(n)$

354. 俄罗斯套娃信封问题

◎ 第一次 hard 题 100%

https://leetcode-cn.com/problems/russian-doll-envelopes/

题目描述

Note

给你一个二维整数数组 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 <= 5000$
$envelopes[i].length == 2$
$1 <= wi, hi <= 10^4$

思路

二维最长递增子序列问题
优先对 x[:][0] 列排序，对 x[:][1] 列次优排序
对 x[:][1] 列求最长递增子序列

代码

Python

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        def binary_search(nums, target):
            l, r = 0, len(nums)-1
            while l < r:
                mid = l + (r-l)//2
                if nums[mid] < target:
                    l = mid + 1
                else:
                    r = mid
            return l
        
        def lis(nums):
            d = []
            for num in nums:
                if not d or d[-1] < num:
                    d.append(num)
                    continue
                idx = binary_search(d, num)
                d[idx] = num
            return len(d)

        envelopes.sort(key=lambda x:(x[0],-x[1]))
        return lis([h for _, h in envelopes])

复杂度

时间复杂度：$O(nlogN)$
空间复杂度：$O(n)$

最长递增子序列

目录

674. 最长连续递增序列

题目描述

思路

代码

复杂度

300. 最长递增子序列

题目描述

思路

代码

复杂度

354. 俄罗斯套娃信封问题

题目描述

思路

代码

复杂度