【算法日记】Day 9 动态规划专题——最长递增子序列问题及扩展

Abstract#动态规划#最长递增子序列#二分查找#排序1. 题目题目LeetCode 354. 俄罗斯套娃信封核心思路先将信封按宽度升序排序若宽度相同则按高度降序排序。然后对排序后的高度序列求最长递增子序列LIS的长度即为最多能套娃的信封数。宽度相同按高度降序是为了避免相同宽度的信封互相套娃因为宽度相等不能嵌套降序后高度不会递增从而不会错误地计入LIS。复杂度时间复杂度O ( n l o g n ) O(n log n)O(nlogn)排序O ( n l o g n ) O(n log n)O(nlogn) LIS二分O ( n l o g n ) O(n log n)O(nlogn)空间复杂度O ( n ) O(n)O(n)存储 ends 数组。2. 代码classSolution{public:boolcompare(vectorinta,vectorintb){returna[0]!b[0]?a[0]b[0]:a[1]b[1];}// 二分查找第一个num的位置ends数组递增intBinarySearch(vectorintends,intlen,intnum){intl0,rlen-1,m,ans-1;while(lr){ml((r-l)1);if(ends[m]num){rm-1;ansm;}elselm1;}returnans;}intmaxEnvelopes(vectorvectorintenvelopes){intnenvelopes.size();sort(envelopes.begin(),envelopes.end(),compare);vectorintends(n);// ends[i]表示长度为i 1的递增子序列的最小末尾值intlen0;for(inti0,find;in;i){findBinarySearch(ends,len,envelopes[i][1]);if(find-1)ends[len]envelopes[i][1];elseends[find]envelopes[i][1];}returnlen;}};3. 心得LIS问题优化该问题本质上是一个二维偏序LIS问题在题目条件下可以借助排序转化为简单的一维LIS问题。尽管都是一维但与模板题见相关题目第一题不同的是该问题不能直接用经典DP数组来求解时间复杂度为O ( n 2 ) O(n^2)O(n2)在该题的数据量下会超时。应该使用LIS的优化解法引入数组ends表示各个长度的递增子序列的最小末尾值随后在遍历主数组的过程中抓住ends数组递增的特点利用二分搜索寻找最左侧大于等于主数组当前位置数的元素并由此更新ends最终ends的长度即为LIS的长度。传参避免拷贝在自定义比较函数compare或二分查找函数中参数应使用引用传递如vectorint a而不是值传递。如果传值每次调用都会拷贝整个vector产生额外的内存和时间开销对于大数据量如n10 5 10^5105会直接内存超限。另外一种比较直接的解决方案是设置全局变量避免传参。静态比较函数自定义比较函数在类内需要声明为static否则sort无法调用。4. 相关题目LeetCode 300. 最长递增子序列LeetCode 646. 最长数对链LeetCode 2111. 使数组 K 递增的最少操作次数