LeetCode 354. Russian Doll Envelopes
You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.
What is the maximum number of envelopes can you Russian doll? (put one inside other)
Example:
Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
大信封装小信封，为了方便DP，先进行排序，按宽度升序。出现了问题，高度怎么排呢？如果是单纯的暴力DP，那两个循环，高度其实是无所谓的，满足宽度、高度都更大就行了，怎么排都可以，如下：
class Solution {
public:
int maxEnvelopes(vector<pair<int, int>>& envelopes) {
int res = 0, n = envelopes.size();
vector<int> dp(n, 1);
sort(envelopes.begin(), envelopes.end());
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (envelopes[i].first > envelopes[j].first && envelopes[i].second > envelopes[j].second) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
res = max(res, dp[i]);
}
return res;
}
};
但是其实可以优化速度。首先知道，宽度相同的一组信封肯定只能用一张。那用那张呢？应该趋向于高度尽量小的那张，这样更可能套的上宽度更大的信封。
因为宽度已经是升序了，我们实际上只需要用一个数组按升序保存所有高度就可以了（实际上是一个大顶堆）。那问题来了，万一有很多张同一宽度不同高度的信封那不是没法区分，会全被加进来了吗？很简单，我们排序的时候加一个规则——宽度相同的信封按高度降序排。这样，首先加进来的一定是同一宽度中最高的信封，同一宽度下后加的一定是比较短的信封，自然不可能把前面的装下，也就不会出现同一宽度加多次的情况。
但前面说了，同一宽度下我们其实最希望用最短的那张，更短的我们是希望拿来把最外面那张替掉的。那么我们拿着这张更短信封的高度在数组（堆）中二分搜索，搜索的其实是第一个大于此高度的位置，然后把这个位置上的高度替掉。如果是能满足要求（比最外层小比次外层大），那自然可以把最外面这张替掉。
这里可能有疑问，那万一替掉的不是最外层，把里面宽度更小的替掉了呢？这里用的DP方法确实存在这样的问题，数组里存储的并不是实际可行的一个套娃方案，但是我们的信封其实并不关心里面啊，最外面一个是对的就行了，加上我们的高度是降序排列的，替也只能往前面小的替，也就是往里层替，不会影响最外层，更不会影响我们最关心的问题——能套几层。所以这一方法是完全可行的，完整代码如下：
public class Leet354_RussianDollEnvelopes {
public int maxEnvelopes(int[][] envelopes) {
//虽然Java类库用起来简单，但还是会比写lambda慢一点
//Arrays.sort(envelopes, Comparator.comparingInt((int[] array) -> array[0])
// .thenComparing(array -> -array[1]));
Arrays.sort(envelopes, (e1, e2) -> {
if (e1[0] != e2[0]) {
// 宽度升序
return e1[0] - e2[0];
} else {
// 高度降序
return e2[1] - e1[1];
}
});
// 由于主序是宽度，只要关注高度就可以了
List<Integer> dp = new ArrayList<>();
for (int[] envelope : envelopes) {
int left = 0, right = dp.size(), t = envelope[1];
while (left < right) {
int mid = left + (right - left) / 2;
if (dp.get(mid) < t)
left = mid + 1;
else
right = mid;
}
if (right >= dp.size())
dp.add(t);
else
dp.set(right, t);
}
return dp.size();
}
public static void main(String[] args) {
int[][] env = {{2,100},{3,200},{4,300},{5,500},{5,400},{5,250},{6,370},{6,360},{7,380}};
Leet354_RussianDollEnvelopes ins = new Leet354_RussianDollEnvelopes();
System.out.println(ins.maxEnvelopes(env));
}
}
这个其实就是Leet300用的方法。