解答几个疑惑点:
1. 这里是如何转换为找最长上升子序列问题的?
-
只有宽高都大于另一个信封时才能套娃, 所以可以按 宽度由小到大, 宽度相等时高度由大到小排序。(高度降序的原因在下面)
-
由于我们先按照宽度升序排序,所以就只需要关注高度了,因为高度由大到小, 所以肯定不能接到前一个宽度相等的信封里 ,这就转变求对: 高度的最长上升子序列
2. 为什么高度这里要逆序排序?
-
如果高度不逆序的话(也就是高度正序),p 数组就会出现:在相同 w 情况下,最小的 h 已经出现在 p 数组中了,更大的 h 可能出现在 p 数组靠后的位置(从相同 w 和更小 h 状态转移而来),这违背了题目原义。
-
如果高度逆序,p 数组就会出现:在相同的 w 情况下,最大的 h 最先占据 p 数组中的位置,所以后面的 h 只能出现在 <= 当前位置,由于最大的 h 是由其他不同 w 状态转移而来,这就不会影响最大 h 的值的正确性,所以这个才符合。
class Solution {
public int maxEnvelopes(int[][] w) {
int n = w.length;
int[] f = new int[n];
Arrays.sort(w, (o1, o2) -> {
if (o1[0] == o2[0]) return o2[1] - o1[1];
return o1[0] - o2[0];
});
// p[i]:表示在长度都为 i 的情况下,存放的最小值。
// 因为存放最小值可以让 p[i] 后面的 p[...] 凑出更大的值
int[] p = new int[n + 1];
int len = 0;
for (int i = 0; i < n; i++) {
f[i] = 1;
int l = 0, r = len;
while (l < r) {
int mid = l + r + 1 >> 1;
if (p[mid] < w[i][1]) l = mid;
else r = mid - 1;
}
p[r + 1] = w[i][1];
len = Math.max(len, r + 1);
}
return len;
}
}