题解 | #信封嵌套问题#
信封嵌套问题
http://www.nowcoder.com/practice/9bf77b5b018d4d24951c9a7edb40408f
信封嵌套问题
问题描述：给n个信封的长度和宽度。如果信封A的长和宽都小于信封B，那么信封A可以放到信封B里，请求出信封最多可以嵌套多少层。
示例1
输入：[[3,4],[2,3],[4,5],[1,3],[2,2],[3,6],[1,2],[3,2],[2,4]]
返回值：4
说明：从里到外分别是{1，2}，{2，3}，{3，4}，{4，5}。
示例2
输入：[[1,4],[4,1]]
返回值：1
方法一
思路分析
首先对所给的信封进行排序，我们需要按照信封的长度length进行升序排序，如果两个信封的长度相同则可以按照其宽度width进行降序排序，之后对宽度寻找最长递增序列，在寻找最长递增序列时使用动态规划的办法。这里需要解释为什么在长度相同的时候要按照其宽度进行降序排序，因为长度相同的信封无法进行嵌套，因此长度相同的信封只能选取一个，如果按照升序排序，那么就会造成无法嵌套但仍归纳为递增序列中造成错误。
动态规划构造最长自增序列的过程以及转移方程：
- 设置$dp[i]$表示第i个位置上的最长递增序列长度，那么初始化所有位置$dp[i]=1$只有一个元素
- 寻找$i$位置上的最长递增序列，需要寻找该位置之前左侧所有的元素，如果是递增的，那么$dp[i]=max(dp[i],dp[j]+1)$，其中$j<i$
- 最后返回$dp$数组中的最大值即为最长递增序列的长度也即信封嵌套的层数
图解
C++核心代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param letters intvector<vector<>>
* @return int
*/
static bool cmp(const vector<int> a,const vector<int> b)
{
if(a[0]==b[0]) return a[1]>=b[1];//长度相同，宽度按照降序排序
else return a[0]<b[0];//长度按照升序排序
}
int maxLetters(vector<vector<int> >& letters) {
// write code here
if(letters.empty()) return 0;
int n=letters.size();
sort(letters.begin(),letters.end(),cmp);//对数组元素排序
vector<int > dp(n,0);//设置最长递增序列的数组
dp[0]=1;
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)//从i位置之前的位置寻找可能的最长递增序列
{
if(letters[i][1]>=letters[j][1])
{
dp[i]=max(dp[i],dp[j]+1);//动态规划的办法寻找每个位置的最长子序列数组
}
}
}
return *max_element(dp.begin(),dp.end());
}
}; 复杂度分析
- 时间复杂度：两层循环，循环次数为$1+2+3+4+n-1=n*(n-1)/2$，因此时间复杂度为$O(n^2)$
- 空间复杂度：借助于一个辅助数组用于存放每个位置的最长递增序列长度，因此空间复杂度为$O(n)$
方法二
思路分析
上面的方法时间复杂度高不符合规定的要求，为提高速度，采取以空间换时间的方式，使用二分法的办法优化动态规划，在求解$dp[i]$的过程中使用二分法的办法优化。先设置一个长度为n的数组ends，初始时ends[0]=letters[0][1]，其他位置上的值为0，$ends[b]=c$表示遍历到目前为止，在所有长度为b+1的递增序列中，最小的结尾数是c。每次ends数组存储当前位置之前所有长度为b+1的递增序列中，最小的结尾数是c的元素
图解
C++ 核心代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param letters intvector<vector<>>
* @return int
*/
static bool cmp(const vector<int> a,const vector<int> b)
{
if(a[0]==b[0]) return a[1]>=b[1];//长度相同，宽度按照降序排序
else return a[0]<b[0];//长度按照升序排序
}
int maxLetters(vector<vector<int> >& letters) {
// write code here
if(letters.empty()) return 0;
int n=letters.size();
sort(letters.begin(),letters.end(),cmp);//对数组元素排序
vector<int > dp(n,1);//设置最长递增序列的数组
dp[0]=1;
vector<int> ends(n);
ends[0] = letters[0][1];//ends[b]=c，则表示遍历到目前为止，在所有长度为b+1的递增序列中，最小的结尾数是c
int right = 0;
int ll = 0;
int rr = 0;
int mm = 0;
for (int i = 1; i < n; ++i)
{
ll = 0;
rr = right;
while (ll <= rr)
{
mm = (ll + rr) / 2;
if (letters[i][1] > ends[mm])
{
ll = mm + 1;
}
else
{
rr = mm - 1;
}
}
right = max(right, ll);
ends[ll] = letters[i][1];
dp[i] = ll + 1;
}
return *max_element(dp.begin(),dp.end());//返回最长递增序列的长度
}
}; 复杂度分析
- 时间复杂度：循环遍历一次，每次查找为二分查找，因此时间复杂度为
- 空间复杂度：借助于两个数组，因此空间复杂度为$O(n)$