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 比较大小，所以需要知道当前下标以外，还需要知道上一个数字的下标。

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

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

（一）记忆化搜索 「思路一」

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

回溯三问：{① 子问题？ 以nums[i] 结尾的 LIS 长度② 当前操作？枚举 nums[j]③ 下一个子问题？以nums[j] 结尾的 LIS 长度}

class Solution:#  记忆化搜索def lengthOfLIS(self, nums: List[int]) -> int:n = len(nums)@cachedef dfs(i):res = 0for j in range(i):if nums[j] < nums[i]:res = max(res,dfs(j))return res + 1# ans = 0# for i in range(n):#     ans = max(ans,dfs(i))# return ansreturn 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]

（二） 记忆化搜索，改成递推 「思路二」

class Solution:#  记忆化搜索 改成递推def lengthOfLIS(self, nums: List[int]) -> int:n = len(nums)f = [0] * nfor i in range(n):for j in range(i):if nums[j] < nums[i]:f[i] = max(f[i],f[j]);f[i] += 1;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的末尾元素的最小值

例如 nums = [1,6,7,2,4,5,3]g = [1]          // 第一步插入1， g = [1]g = [1,6]        // 第二步插入6， g = [1,6]g = [1,6,7]      // 第三步插入7， g = [1,6,7]g = [1,2,7]      // 第四步插入2， g = [1,2,7]g = [1,2,4]      // 第五步插入4， g = [1,2,4]g = [1,2,4,5]    // 第六步插入5， g = [1,2,4,5]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 的末尾

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

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

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

Python 代码: 

class Solution:# 贪心 + 二分def lengthOfLIS(self, nums: List[int]) -> int:g = []for x in nums:j = bisect_left(g,x)if j == len(g):g.append(x)else:g[j] = xreturn len(g)

• 时间复杂度：O(nlogn)    
• 空间复杂度：O(n)

 C++ 代码：

class Solution {
public:// 贪心 + 二分int lengthOfLIS(vector<int>& nums) {vector<int> g;for(int x:nums) {int j = lower_bound(g.begin(), g.end(), x) - g.begin();if(j == g.size()) g.push_back(x);else g[j] = x;}return g.size();}
};

思考：空间复杂度还能能进一步优化吗？ 可以！！！

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

Python 代码:  

class Solution:# 贪心 + 二分 (优化空间复杂度) O(1)def lengthOfLIS(self, nums: List[int]) -> int:ng = 0for x in nums:j = bisect_left(nums,x,0,ng)if j == ng:nums[ng] = xng+=1else:nums[j] = xreturn ng

• 时间复杂度：O(nlogn)    
• 空间复杂度：O(1)

 C++ 代码： 

class Solution {
public:// 贪心 + 二分 int lengthOfLIS(vector<int>& nums) {int ng = 0;for(int x:nums) {int j = lower_bound(nums.begin(), nums.begin() + ng, x) - nums.begin();if(j == ng) {nums[ng] = x;ng+=1;}else nums[j] = x;}return ng;}
};

>>拓展思考🤔

变形：如果LIS 中可以有相同元素呢？（非严格递增）那么g是非严格递增序列
在修改的是偶，和nums[i] 相同的 g[j] 就不同改了，而是修改 > nunms[i]
的第一个 g[j]
例如 nums = [1,6,7,2,2,5,2]g = [1]g = [1,6]g = [1,6,7]g = [1,2,7]g = [1,2,2]g = [1,2,2,5]g = [1,2,2,2]

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

def lengthOfLIS(self, nums: List[int]) -> int:ng = 0for x in nums:j = bisect_right(nums,x,0,ng)if j == ng:nums[ng] = xng+=1else:nums[j] = xreturn ng

class Solution {
public:// 贪心 + 二分 int lengthOfLIS(vector<int>& nums) {int ng = 0;for(int x:nums) {int j = upper_bound(nums.begin(), nums.begin() + ng, x) - nums.begin();if(j == ng) {nums[ng] = x;ng+=1;}else nums[j] = x;}return ng;}
};

>>参考和推荐视频： 

最长递增子序列【基础算法精讲 20】_哔哩哔哩_bilibilihttps://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