合肥城市建设网站,互联网行业都有哪些专业,Wordpress球队网站,广东网站建设seo优化300. 最长递增子序列 - 力扣#xff08;LeetCode#xff09;
给你一个整数数组 nums #xff0c;找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列#xff0c;删除#xff08;或不删除#xff09;数组中的元素而不改变其余元素的顺序。例如#xff…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分析
递增子序列 ISIncreasing Subsequence最长递增子序列 LISLongest Increasing SubsequenceO(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] 表示长度为 i1 的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(vectorint nums) {vectorint 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] xng1else:nums[j] xreturn ng
时间复杂度O(nlogn) 空间复杂度O(1) C 代码
class Solution {
public:// 贪心 二分 int lengthOfLIS(vectorint 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;ng1;}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] xng1else:nums[j] xreturn ng
class Solution {
public:// 贪心 二分 int lengthOfLIS(vectorint 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;ng1;}else nums[j] x;}return ng;}
};
参考和推荐视频
最长递增子序列【基础算法精讲 20】_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1ub411Q7sB/?vd_sourcea934d7fc6f47698a29dac90a922ba5a3
此题动态规划详解可看我的往期文章
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?spm1001.2014.3001.5501
