当前位置：首页 > news >正文

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

news 2026/6/6 22:15:53

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(vector<int>&a,vector<int>&b){returna[0]!=b[0]?a[0]<b[0]:a[1]>b[1];}// 二分查找第一个>=num的位置（ends数组递增）intBinarySearch(vector<int>&ends,intlen,intnum){intl=0,r=len-1,m,ans=-1;while(l<=r){m=l+((r-l)>>1);if(ends[m]>=num){r=m-1;ans=m;}elsel=m+1;}returnans;}intmaxEnvelopes(vector<vector<int>>&envelopes){intn=envelopes.size();sort(envelopes.begin(),envelopes.end(),compare);vector<int>ends(n);// ends[i]表示长度为i + 1的递增子序列的最小末尾值intlen=0;for(inti=0,find;i<n;++i){find=BinarySearch(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或二分查找函数中，参数应使用引用传递（如vector<int>& a）而不是值传递。如果传值，每次调用都会拷贝整个vector产生额外的内存和时间开销，对于大数据量（如n=10 5 10^5105）会直接内存超限。另外一种比较直接的解决方案是设置全局变量，避免传参。
静态比较函数：自定义比较函数在类内需要声明为static，否则sort无法调用。