354. Russian Doll Envelopes
Description
Intuition
这题有点意思，先按照primaryKey: e[0], SecondaryKey: e[1]，然后按照300 LIS对高度进行操作tails
Proof
当按照上述排序后，会有如下的保证
- 后面的width必然大于等于之前的，也就是tails里的所有高度都是可以用的
- 大于的时候必然可以塞下去
- 等于的时候，那么现在的height 必然比之前的小于等于
你可以认为tails下面有各种分类
public int maxEnvelopes(int[][] envelopes) {
if (envelopes == null || envelopes.length == 0) {
return 0;
}
Arrays.sort(envelopes, new Comparator<int[]>() {
@Override
public int compare(final int[] a, final int[] b) {
int cmp = Integer.compare(a[0], b[0]);
if (cmp == 0) {
return Integer.compare(b[1], a[1]);
}
return cmp;
}
});
final int[] tails = new int[envelopes.length];
tails[0] = envelopes[0][1];
int right = 0;
for (int[] e : envelopes) {
int insertPoint = getInsertionPoint(tails, e[1], right);
tails[insertPoint] = e[1];
if (insertPoint == right + 1) {
right++;
}
}
return right + 1;
}
private int getInsertionPoint(final int[] tails, final int target, int right) {
final int insertPoint = Arrays.binarySearch(tails, 0, right + 1, target);
if (insertPoint < 0) {
return -(insertPoint + 1);
}
return insertPoint;
}