最长递增子序列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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 暴力解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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 动态规划 + 二分

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


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. 俄罗斯套娃信封问题

题目描述

思路

代码

复杂度

最长递增子序列

目录

674. 最长连续递增序列

题目描述

思路

代码

复杂度

300. 最长递增子序列

题目描述

思路

代码

复杂度

354. 俄罗斯套娃信封问题

题目描述

思路

代码

复杂度

相关文章：