- 链接：https://leetcode.cn/problems/russian-doll-envelopes/description/
难点 #
第一个难点在于如何同时控制 $w_i$ 和 $h_i$ 两个维度，很自然地想到先把一个维度排序，然后只需要考虑另一个维度最长递增子序列就行了。
这时候就有第二个难点了，如果在 $w_i$ 这个维度，存在两个值相同的情况怎么处理，需要将 $w_i$ 相同的 $h_i$ 从高到低排序，这样相同 $w_i$ 的部分就不会相互影响。
做完了 $w_i$ 的内容，就只需要考虑 $h_i$ 的最长递增子序列就行了，这时候就是一个动态规划，还是三个问题，
- $dp[i]$ 是 $h$ 的前 $i$ 个元素可以组成的最长严格递增子序列的长度；
- 所有的 $dp[i]$ 初始化为 1；
- 状态转移方程：$dp[i]=max_{j<i \land dp[j]<dp[i]} {dp[j]} + 1$ 。
代码 #
class Solution {
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, new Comparator<int[]>() {
public int compare(int[] e1, int[] e2) {
if(e1[0] == e2[0]) {
return e2[1] - e1[1];
}
return e1[0] - e2[0];
}
});
int n = envelopes.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int ans = 1;
for(int i = 1; i < n; i++) {
for(int j = 0; j < i; j++) {
if(envelopes[i][1] > envelopes[j][1]) {
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
ans = Math.max(dp[i], ans);
}
return ans;
}
}
本来以为这样就结束了，但是还是出了意外，报 TLE ，之前的 sort 的时间已经没办法优化了，就只能优化后面的动态规划了。
二分优化 #
设 $f[j]$ 表示 $h$ 的前 $i$ 个元素可以组成的长度为 $j$ 的最长严格递增子序列的末尾元素的最小值，如果不存在长度为 $j$ 的最长严格递增子序列，对应的 $f$ 值无定义。在定义范围内，可以看出 $f$ 值是严格单调递增的，因为越长的子序列的末尾元素显然越大。
考虑当前的 $h[i]$
- 若 $h[i] > f_{last}$ ，那么直接在 f 最后放 $h[i]$ 就行，
- 否则，我们在 $f$ 中找出比 $h[i]$ 严格小的最大元素，把 $h[i]$ 放在它后面。
代码 #
class Solution {
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, new Comparator<int[]>() {
public int compare(int[] e1, int[] e2) {
if(e1[0] == e2[0]) {
return e2[1] - e1[1];
}
return e1[0] - e2[0];
}
});
int n = envelopes.length;
List<Integer> f = new ArrayList<Integer>();
f.add(envelopes[0][1]);
for (int i = 1; i < n; ++i) {
int num = envelopes[i][1];
if (num > f.get(f.size() - 1)) {
f.add(num);
} else {
int index = binarySearch(f, num);
f.set(index, num);
}
}
return f.size();
}
public int binarySearch(List<Integer> f, int target) {
int low = 0, high = f.size() - 1;
while (low < high) {
int mid = (high - low) / 2 + low;
if (f.get(mid) < target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
}
