没有公众号建微信网站,购物商城外贸网站建设,整合营销传播简称,pc网站制作APP给你一个整数数组 nums #xff0c;找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列#xff0c;删除#xff08;或不删除#xff09;数组中的元素而不改变其余元素的顺序。例如#xff0c;[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1#…给你一个整数数组 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 -1e4 nums[i] 1e4
进阶思考
你能将算法的时间复杂度降低到 O(n log(n)) 吗?
题解:
一共有两种写法: 第一种的时间复杂度是O(n ^ 2), 第二种的时间复杂度是O(n * logn)
第一种写法
动态规划的题
f[i]: 只考虑前 i 个数(包含i), 并且以第i个数结尾的子序列的所有方案的子序列长度的最大值
状态表示:
集合: 只考虑前 i 个数(包含i), 并且以第i个数结尾的子序列的所有方案属性: 子序列长度的最大值
状态计算:
对于第 i 个数的状态转移方程是:
只有一个第 i 个数, 此时f[i] 1;以第1个数结尾的基础上再选第i个数尾结尾, 以第2个数结尾的基础上再选第i个数结尾…以第i - 1个数结尾的基础上再选第i个数结尾,上面所有情况的长度取max就是f[i], 也就是 f[j] 1, 因为选第i个数, 所有长度加1, j 属于(0, i)
看不懂状态计算的话, 一定要多理解状态表示, 理解了状态表示, 就可以理解状态计算
ac代码 时间复杂度(O(n ^ 2))
class Solution {
public:int lengthOfLIS(vectorint nums) {if (nums.size() 0) return 0;// 以第i个数结尾的最长上升子序列 maxvectorint f(nums.size(), 0);for (int i 0; i nums.size(); i ){f[i] 1; // 只有第i个数的情况, 也就是状态计算1for (int j 0; j i; j ) // 状态计算2if (nums[i] nums[j]) f[i] max(f[i], f[j] 1); // 要加上判断, 使子序列满足严格的单调递增}int res 0; // 最长上升子序列不一定会选最后一个, 也不一定会选倒数第二个..., 所有最后的答案是f数组中的最大值, 主要还是要理解状态表示for (int i 0; i f.size(); i ) res max(res, f[i]);return res;}
};第二种写法
贪心 二分
子序列长度要想尽可能大, 在相同长度的情况下, 我们要让子序列末尾的元素尽可能小, 这样后面进来的元素才能尽可能地多所以我们维护一个数组 f[i]: 长度为 i 的最长上升子序列末尾的最小值。
对于每个nums[i], 有两种情况
如果nums[i] 比 f[len] 大的话, 直接让 f 的长度 1 然后f[len 1] 的值是nums[i]如果nums[i] 比 f[len] 小的话, 需要从f数组中找到 第一个大于等于 nums[i] 的位置, 并把这个值重新赋值为nums[i]
其实上面的过程更像是我们人来找最长上升子序列的时候的样子
为了让大家更好理解, 这里模拟下下面的一个样例
输入样例: 1 2 3 8 4 5 6 7d[1] nums[0] 1; (初始化)
循环次数 i d的值 len 长度1 d[2] 2; 22 d[3] 3; 33 d[4] 8; 4 4 d[4] 4 4 因为4比8小, 通过二分查找到8的位置, 8在d数组中的下标是4, 所以d[4]的值应该被修改成45 d[5] 5 56 d[6] 6 67 d[7] 7 7ac 代码 时间复杂度O(n * logn)
class Solution {
public:int lengthOfLIS(vectorint nums) {int n nums.size();if (n 0) return 0;vectorint f(n 1, 0); // f下标从1开始int len 1; f[len] nums[0];for (int i 1; i n; i ){if (nums[i] f[len]) f[ len] nums[i];else{int l 1, r len;while (l r) // 查找第一个大于等于nums[i]{int mid l r 1; // 右移一位, 相当于(l r) / 2if (f[mid] nums[i]) l mid 1;else if(f[mid] nums[i]) r mid;}f[l] nums[i];}}return len;}
};对于二分的退出条件的差异:
while(l r) 和 while (l r)
while(l r) 对应的代码, 退出的时候 l r
int l 0, r len;
while (l r){int mid l r 1;if (f[mid] nums[i]) l mid 1;else if(f[mid] nums[i]) r mid;}while (l r)对应的代码, 退出的时候 l r
int l 0, r len;
while (l r){int mid l r 1;if (f[mid] nums[i]) l mid 1;else if(f[mid] nums[i]) r mid - 1;}上面两个代码找到的都是第一个大于等于nums[i]的下标, 但while循环里面略有不同
个人习惯用while(l r), 感觉这种方法里面l和r的边界好理解 if (f[mid] nums[i]) l mid 1; 说明 mid 位置上的数不满足 f[mid] nums[i], 所有要到二分的右边去找并且不包过 mid这个位置的数 else if(f[mid] nums[i]) r mid; 说明 mid 位置上的数可能满足 f[mid] nums[i], 所以要到二分的左边去找, 并且包含mid这个位置上的数
觉得写的不错的话, 点个赞吧~
