NC153 信封嵌套问题
题意
给 个信封的长度和宽度。如果信封
的长和宽都小于信封
，那么信封
可以放到信封
里，请求出信封最多可以嵌套多少层。
本题是魔改的最长递增子序列(LIS)问题，所以最长递增子序列的解法都适用于本题。
但是这题是二维的，如何降维？
我们可以这样思考，不管怎么套娃，最终的答案中一定宽度、长度都是有序的。所以我们可以先对宽度排序（这里需要特殊注意，如果宽度相等，长度要倒序排列，否则会出现[1,2]装入[1,3]的case），这样长度变成无序的了，然后对长度维度求LIS即可。接下来就是复习下LIS的各种思路。
1. 暴力法（不合要求，tle)
枚举每个数选或者不选，再看他们是否单调递增。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param letters intvector<vector<>>
* @return int
*/
using vi = vector<int>;
static bool cmp(const vi a, const vi b) {
return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
}
vi weights; // 把宽度单独挑出来
int cur = 0, res = 0, n; // 记录当前选中了几个数
int maxLetters(vector<vector<int> >& letters) {
// 对长度排序
sort(letters.begin(), letters.end(), cmp);
n = letters.size();
for (auto a : letters) {
// 把宽度单独挑出来
weights.push_back(a[1]);
}
// 回溯法搜索weights的LIS
dfs(0, 0); // 当前枚举第0个元素，上层搜到的最大值是0（因为信封大小都是正数）
return res;
}
void dfs(int u, int last) {
// 搜到第n步，说明weights数组搜完了，可以更新答案
if (u == n) {
res = max(res, cur);
return;
}
int next = weights[u];
if (last < next) { // 要想选第u个元素，需要比前面那个大
cur++; // 选中第u个
dfs(u+1, next);
cur--; // 拿走，回溯
} else {
dfs(u+1, last); // 跳过第u个元素
}
}
};- 时间复杂度：
, 每个数都可能选或不选，所以复杂度是指数级别。
- 空间复杂度：
.
2. 动态规划
当n稍大的时候，方法一显然会TLE. 观察到LIS问题，在所有解当中如果固定了右端点，那么该数后面的数均不受影响，并且每个上升子序列的子序列还是上升子序列，因此可以使用dp来解决。
令dp[i]表示以第i个数为结尾的LIS，注意这里第i个数必须选。那么倒数第二个数有可能在0,....,i-1里面找，且满足a[j] < a[i], 把满足条件的j都找出来，然后把以j为结尾的LIS加上第i个数即可。而以j为结尾的LIS我们已经知道是dp[j]了。
那么可以得到动态规划转移式：
初始化状态，所有dp值均为1，因为至少有他自己。最终的答案为所有dp的最大值。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param letters intvector<vector<>>
* @return int
*/
using vi = vector<int>;
static bool cmp(const vi a, const vi b) {
return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
}
vi weights;
int n;
static const int N = 100; // 题目没说letters数组多大，由于方法一能ac，所以应该很小，不会超过100的。
int dp[N]; // 定义动态规划数组
int maxLetters(vector<vector<int> >& letters) {
sort(letters.begin(), letters.end(), cmp);
n = letters.size();
for (auto a : letters) {
weights.push_back(a[1]);
}
return lis();
}
int lis() {
// 初始值为1
for (int i = 0; i < n; i++)
dp[i] = 1;
// 实现转移过程
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (weights[j] < weights[i]) dp[i] = max(dp[i], dp[j]+1);
}
}
// 找dp数组的最大值，至少是1
int res = 1;
for (int i = 0; i < n; i++)
res = max(res, dp[i]);
return res;
}
};- 时间复杂度：
, 两重关于
的循环。
- 空间复杂度：
, 定义了大小为
3. 单调栈+二分
方法二仍不符合题目要求的复杂度，我们看看还可以怎么优化。
lis问题中，我们每次选择元素的时候，要想让这个数加入到最终的答案中，需要他比左边的数都大，要想得到“更优”的答案，我们需要增长的速度尽量“慢”，而且后放进答案的元素，遇到更优的要先退出来，那这不就是单调栈吗？
所以我们这道题还可以这样做，维护一个单调栈，栈里存储当前的最优解，遍历数组：
- 如果这个数a[i]比栈顶元素大，那么入栈（因为最优解有可能包含该数）
- 如果小，那么在栈里找比a[i]小的最后一个数，并把这个数的后继换为a[i]. 因为这样，是有可能得到一个“更接近最优解”的答案。例如栈中为[5,6,10], 如果我们把10换成8，那么[5,6,8]会比[5,6,10]更能“吸引”更优答案（比如后面有9，可以把9入栈）。
- 每次迭代都要更新答案，如果栈中元素个数大于当前最优解，说明找到了更优解。
第三步中，因为栈中元素严格单调，所以可以使用二分查找优化，用一个图描述上述过程：
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param letters intvector<vector<>>
* @return int
*/
using vi = vector<int>;
static bool cmp(const vi a, const vi b) {
return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
}
vi weights;
int n;
static const int N = 100;
int maxLetters(vector<vector<int> >& letters) {
sort(letters.begin(), letters.end(), cmp);
n = letters.size();
for (auto a : letters) {
weights.push_back(a[1]);
}
return lis();
}
int stk[N], len = 0;
int lis() {
int res = 0;
for (int i = 0; i < n; i++) {
int l = 0, r = len;
while (l < r) {
int mid = l + r + 1 >> 1; // 因为收敛过程是r=mid-1，所以要上取整
// 如果严格小，说明答案不会在mid右侧，可能是mid
if (stk[mid] < weights[i]) l = mid;
// 如果大于或等于，那么比w[i]小的最后一个数一定在mid左侧
else r = mid-1;
}
// 把l后面一个数换为w[i]
stk[l+1] = weights[i];
len = max(len, l + 1); // 如果l=len，那么len更新
res = max(res, len); // 不断更新res=len的最大值
}
return res;
}
};- 时间复杂度：
, 遍历一轮，每轮进行了一次二分查找
- 空间复杂度:
4. 拓展
如果本题不是信封而是箱子（三个属性）呢？那么是不是还可以先求两个维度上的最大嵌套序列？事实上这个思路是错误的，因为两个维度上的最优解不一定能代表在第三个维度也是最优的，换句话说，可能全局最优解投影到两个维度上，却是次优。
如果问题扩展到三维嵌套，就叫二维偏序问题，其中我们面试中较为常见的逆序对就是一种二维偏序。这个问题要用树状数组来做，对树状数组的考察已经远超一般的笔试、面试难度，大家有兴趣可以自行学习。
京公网安备 11010502036488号