• leetCode 300.最长递增子序列 (贪心 + 二分 ) + 图解 + 优化 + 拓展


    300. 最长递增子序列 - 力扣(LeetCode)

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

    >>分析:

    • 递增子序列           IS,Increasing Subsequence
    • 最长递增子序列    LIS,Longest Increasing Subsequence
    • O(n^2)           回溯  -->  记忆化搜索  -->  递推
    • O(nlogn)       贪心 + 二分

    >>思路:

    • 思路 1 不选      为了比大小,需要知道上一个选的数字
    • 思路 2 枚举选哪个     比较当前选得到数字和下一个要选的数字

    >>举个栗子,比如[1,6,7,2,4,5,3]中:

    子序列:就是从数组中选择一些数,且顺序和数组中的顺序是一致的。比如[2,5,3]就是这个数组的一个子序列

    这题中的严格递增子序列,就是要求你选的子序列 右边的元素一定大于左边的元素。比如[1,2,5]就是一个严格递增的子序列。我们要做的就是在所有严格递增子序列中。找到最长的那个子序列的长度。比如[1,2,4,5]就是最长递增子序列请注意是严格递增的,也就是说不能有相同元素,所以在示例3中,严格递增子序列只有一个元素,由于子序列本质上是数组的一个子集,我们可以考虑用子集型回溯来思考(O_O)?

    对于子集型回溯,我们有「选或不选」 以及 「枚举选哪个」这两种思路,如果倒着思考,假设 3是子序列的最后一个数,考虑选或者不选的话,这前面的数字就需要和 3 比较大小,所以需要知道当前下标以外,还需要知道上一个数字的下标。

    而如果考虑「枚举选哪个」,我们就可以直接枚举前面的比 小的数字,当做子序列的倒数第二个数。那么只需要知道当前所选的数字的下标就好了。

    这样对比,会发现「枚举选哪个」只需要一个参数,比较好写。

    (一)记忆化搜索 「思路一」

    启发思路:枚举 nums[i] 作为 LIS 的末尾元素,那么需要枚举 nums[j] 作为 LIS 倒数第二个元素,其中 j < i 且 nums[j] < nums[i]

    1. 回溯三问:{
    2.     ① 子问题? 以nums[i] 结尾的 LIS 长度
    3.     ② 当前操作?枚举 nums[j]
    4.     ③ 下一个子问题?以nums[j] 结尾的 LIS 长度
    5. }
    1. class Solution:
    2. # 记忆化搜索
    3. def lengthOfLIS(self, nums: List[int]) -> int:
    4. n = len(nums)
    5. @cache
    6. def dfs(i):
    7. res = 0
    8. for j in range(i):
    9. if nums[j] < nums[i]:
    10. res = max(res,dfs(j))
    11. return res + 1
    12. # ans = 0
    13. # for i in range(n):
    14. # ans = max(ans,dfs(i))
    15. # return ans
    16. return max(dfs(i) for i in range(n))
    • dfs(i) = max{dfs(j)} + 1   j < i 且 nums[j] < nums[i]
    • f[i] = max{f[j]} + 1           j < i 且 nums[j] < nums[i]

    (二) 记忆化搜索,改成递推 「思路二」

    1. class Solution:
    2. # 记忆化搜索 改成递推
    3. def lengthOfLIS(self, nums: List[int]) -> int:
    4. n = len(nums)
    5. f = [0] * n
    6. for i in range(n):
    7. for j in range(i):
    8. if nums[j] < nums[i]:
    9. f[i] = max(f[i],f[j]);
    10. f[i] += 1;
    11. return max(f)

     (三)贪心 + 二分

    「思路三」nums 的 LIS 等价于nums 与 排序去重后的 nums的LCS,例如 nums =  [1,3,3,2,4]。排序去重后 = [1,2,3,4]。LCS = [1,3,4] 或者 [1,2,4]

    「思路四」考虑一个简单的贪心,如果我们要使上升子序列尽可能的长,则我们需要让序列上升得尽可能慢,因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

    • 进阶技巧:交换状态与状态值
    • f[i] 表示末尾元素 为 nums[i] 的 LIS长度
    • g[i] 表示长度为 i+1 的IS的末尾元素的最小值
    1. 例如 nums = [1,6,7,2,4,5,3]
    2. g = [1] // 第一步插入1, g = [1]
    3. g = [1,6] // 第二步插入6, g = [1,6]
    4. g = [1,6,7] // 第三步插入7, g = [1,6,7]
    5. g = [1,2,7] // 第四步插入2, g = [1,2,7]
    6. g = [1,2,4] // 第五步插入4, g = [1,2,4]
    7. g = [1,2,4,5] // 第六步插入5, g = [1,2,4,5]
    8. g = [1,2,3,5] // 第七步插入3, g = [1,2,3,5]

    按照这种定义方式,由于没有重叠子问题,是不能算作动态规划的,而变成了一个贪心的问题,接着来研究一下g的性质,看上去 g 是一个严格递增的序列,并且每次要么添加一个数,要么修改一个数,这里就来严格证明一下,通常来说证明算法相关的一些结论,数学归纳法和反证法用的是最多的。这里就用反证法来证明,如果 g 不是严格递增的,比如说 g = [1,6,6] 那么最后的这个 6 肯定会对应一个长为 3 的,末尾为 6 的上升子序列,那第二个数是小于等于5的,而这就和第一个6矛盾了,它表示第二个数最小是6。所以通过反证法,我们可以得出 g 一定是一个严格递增的序列,知道 g 是严格递增的,就可以得出后面的结论了。

    • 推论1:一次只能更新一个位置

            证明:假设更新了两个位置,会导致 g 不是严格递增的,因为单调递增序列不能有相同元素

    • 推论2:更新的位置是第一个 >= nums[i]的数的下标

            如果nums[i] 比 g 的最后一个数都大,那就加到 g 的末尾

    1. 证明:设更新了 g[j],如果g[j] < nums[i],相当于把小的数给变大了,
    2. 这显然不可能。另外,如果 g[j] 不是第一个 >= nums[i]的数,那就破坏
    3. 了 g 的有序性
    4. g = [1,6,7],nums[i] = 2
    5. g = [1,2,7]

    算法g 上用二分查找快速找到第一个 >= nums[i] 的下标j,如果 j 不存在,那么nums[i]直接加到 g 末尾,否则修改 g[j] nums[i]

    注意这个算法按分类的话,算「贪心 + 二分」

    Python 代码: 

    1. class Solution:
    2. # 贪心 + 二分
    3. def lengthOfLIS(self, nums: List[int]) -> int:
    4. g = []
    5. for x in nums:
    6. j = bisect_left(g,x)
    7. if j == len(g):
    8. g.append(x)
    9. else:
    10. g[j] = x
    11. return len(g)
    • 时间复杂度:O(nlogn)    
    • 空间复杂度:O(n)

     C++ 代码:

    1. class Solution {
    2. public:
    3. // 贪心 + 二分
    4. int lengthOfLIS(vector<int>& nums) {
    5. vector<int> g;
    6. for(int x:nums) {
    7. int j = lower_bound(g.begin(), g.end(), x) - g.begin();
    8. if(j == g.size()) g.push_back(x);
    9. else g[j] = x;
    10. }
    11. return g.size();
    12. }
    13. };

    思考:空间复杂度还能能进一步优化吗? 可以!!!

    >>优化空间复杂度:O(1)

    Python 代码:  

    1. class Solution:
    2. # 贪心 + 二分 (优化空间复杂度) O(1)
    3. def lengthOfLIS(self, nums: List[int]) -> int:
    4. ng = 0
    5. for x in nums:
    6. j = bisect_left(nums,x,0,ng)
    7. if j == ng:
    8. nums[ng] = x
    9. ng+=1
    10. else:
    11. nums[j] = x
    12. return ng
    • 时间复杂度:O(nlogn)    
    • 空间复杂度:O(1)

     C++ 代码: 

    1. class Solution {
    2. public:
    3. // 贪心 + 二分
    4. int lengthOfLIS(vector<int>& nums) {
    5. int ng = 0;
    6. for(int x:nums) {
    7. int j = lower_bound(nums.begin(), nums.begin() + ng, x) - nums.begin();
    8. if(j == ng) {
    9. nums[ng] = x;
    10. ng+=1;
    11. }
    12. else nums[j] = x;
    13. }
    14. return ng;
    15. }
    16. };

    >>拓展思考🤔

    1. 变形:如果LIS 中可以有相同元素呢?(非严格递增)那么g是非严格递增序列
    2. 在修改的是偶,和nums[i] 相同的 g[j] 就不同改了,而是修改 > nunms[i]
    3. 的第一个 g[j]
    4. 例如 nums = [1,6,7,2,2,5,2]
    5. g = [1]
    6. g = [1,6]
    7. g = [1,6,7]
    8. g = [1,2,7]
    9. g = [1,2,2]
    10. g = [1,2,2,5]
    11. g = [1,2,2,2]

    要改的是大于2的第一个数,具体的证明方式和上面是一样的。对应到代码上,在python中就是把 bisect_left 改成 bisect_right,在C++中就是改成upper_bound

    1. def lengthOfLIS(self, nums: List[int]) -> int:
    2. ng = 0
    3. for x in nums:
    4. j = bisect_right(nums,x,0,ng)
    5. if j == ng:
    6. nums[ng] = x
    7. ng+=1
    8. else:
    9. nums[j] = x
    10. return ng
    1. class Solution {
    2. public:
    3. // 贪心 + 二分
    4. int lengthOfLIS(vector<int>& nums) {
    5. int ng = 0;
    6. for(int x:nums) {
    7. int j = upper_bound(nums.begin(), nums.begin() + ng, x) - nums.begin();
    8. if(j == ng) {
    9. nums[ng] = x;
    10. ng+=1;
    11. }
    12. else nums[j] = x;
    13. }
    14. return ng;
    15. }
    16. };

    >>参考和推荐视频: 

    最长递增子序列【基础算法精讲 20】_哔哩哔哩_bilibiliicon-default.png?t=N7T8https://www.bilibili.com/video/BV1ub411Q7sB/?vd_source=a934d7fc6f47698a29dac90a922ba5a3

    >>此题动态规划详解,可看我的往期文章:

    leetCode 300.最长递增子序列 动态规划 + 图解_呵呵哒( ̄▽ ̄)"的博客-CSDN博客j 其实就是遍历 0 到 i-1,那么是从前向后,还是从后到前都可以,只要是 0 到 i-1 的元素都遍历了就可以,所以习惯从前向后遍历。dp[i] 是 由 0 到 i-1 各个位置的最长递增子序列 推导出来,那么遍历 i 一定是从前向后遍历。“子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序”dp[i]表示 i 之前包括 i 的以 nums[i] 结尾的最长递增子序列的长度。最长递增子序列是 [2,3,7,101],因此长度为 4。是数组 [0,3,1,6,2,2,7]https://blog.csdn.net/weixin_41987016/article/details/133636345?spm=1001.2014.3001.5501

  • 相关阅读:
    Anaconda、conda、pip的区别
    实验2.6.3 函数拓展练习
    时钟的同步与异步问题
    Pandas数据分析开发实战博文集锦
    μCOS-Ⅲ中断管理,这样理解非常简单!
    ROS1云课→19仿真turtlebot(stage)
    彻底理解闭包实现原理
    【3D 图像分割】基于 Pytorch 的 VNet 3D 图像分割1(综述篇)
    python tempfile 模块使用
    基于aarch64分析kernel源码 六:kernel_init进程(1号进程)、kthreadd进程(2号进程)
  • 原文地址:https://blog.csdn.net/weixin_41987016/article/details/133647933