My code:
public class Solution {
public int maxEnvelopes(int[][] envelopes) {
if (envelopes == null || envelopes.length == 0 || envelopes[0].length == 0) {
return 0;
}
Arrays.sort(envelopes, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if (a[0] != b[0]) {
return a[0] - b[0];
}
else {
return b[1] - a[1];
}
}
});
List<Integer> rights = new ArrayList<Integer>();
for (int i = 0; i < envelopes.length; i++) {
if (rights.size() == 0 || rights.get(rights.size() - 1) < envelopes[i][1]) {
rights.add(envelopes[i][1]);
}
else {
int begin = 0;
int end = rights.size() - 1;
while (begin <= end) {
int mid = begin + (end - begin) / 2;
if (rights.get(mid) < envelopes[i][1]) {
begin = mid + 1;
}
else if (rights.get(mid) > envelopes[i][1]) {
end = mid - 1;
}
else {
begin = mid;
break;
}
}
rights.set(begin, envelopes[i][1]);
}
}
return rights.size();
}
}
reference:
http://www.programcreek.com/2016/08/leetcode-russian-doll-envelopes-java/
这道题目没能做出来。看了解法，还是很精彩的。
先按照width大小排序，升序。
再按照height大小排序，降序。
我们可以保证，下一个envelope,他的width一定是当前最大。
但是他的height,并不确定，可能很小，可能很大。
我们需要不断更新这个右侧。
如图：
FullSizeRender 3.jpg
具体自己理解吧。
Anyway, Good luck, Richardo! -- 10/12/2016
