先来看一下题
题意：
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)
样例：
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]).
这个题的大意是这样的：给定一系列有大小的信封，请问像俄罗斯娃娃装起来，最多可以装几个，相同宽或者高的信封不能装。
1.动态规划(超时)
刚刚看到这个题时，想到的是动态规划，因为自己的动态比较薄弱，因此更加想要动态规划做了。于是乎，经过填表，找出了动态规划方程。先说一下思想：我们遍历信封，看看当前当前要装其他信封的信封能装下的最大个数，说得很抽象，看一张表：
但是这里需要注意的是：这里信封的顺序是条件的，我们必须按照宽(也就是说，第一个长度)的升序排序，高升序和降序都行。因为我们必须先把小信封的最大值求出，后面大信封在装小信封时，取得的最大值才是正确的；否则，我们先按照小信封的最大值(没有求)，求大信封的最大值，如果之后小信封的最大值改变，但是大信封的最大值没有更新。
public static int maxEnvelopes(int[][] envelopes) {
if (envelopes == null || envelopes.length == 0)
return 0;
//排序，按照宽的升序和高的降序排序(如果宽相同的话，则按宽的高的降序排序)
Arrays.sort(envelopes, (a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0];
} else {
return a[1] - b[1];
}
});
int max = 1;
int[] a = new int[envelopes.length];
//这里将数组初始化为1，上图的表中是0，如果这里初始化为0话，最后max需要加1
Arrays.fill(a, 1);
for (int i = 0; i < envelopes.length; i++) {
for (int j = 0; j < i; j++) {
//当符合要求是在选择更新a表
if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
a[i] = Math.max(a[i], 1 + a[j]);
if (a[i] > max) {
max = a[i];
}
}
}
}
return max;
}
2.二分法
感觉动态已经能够解决了，其实不然，动态规划也超时了。具体在哪里超时的，我也不太知道，估计是在两重for循环那里超时了，后面在网上找到了二分法的解决办法
(1).前提
二分法的排序必须按照宽的升序，和高的降序来排。至于为什么呢？后面再说。例如：原来的序列：[[5,4],[6,4],[6,7],[2,3],[6,8],[7,8],[1,3]]，排序之后：[[1,3],[2,3],[5,4],[6,8],[6,7],[6,4],[7,8]]
(2).思路
首先我们用一个List集合来保存每个加进来信封的高(第二个数)，当要进来的那个信封的高比List集合的最后数据大的话，则将这个高加入List集合，这是因为经过我们之前的排序，如果一个信封的高大于前一个信封的高，必定这个信封的宽也大于前一个的宽。可能看不太懂，如图所示：
但是如果进来的高比最后一个数据小或者等于呢？首先肯定不能加到集合中去，那为什么会替换(后面代码中会有替换的操作)。想一下，我们是按照宽的升序排序，后面加入来的信封肯定大于或者等于前面加进去的信封的宽；后面进来信封的高小于或者等于时，有两种情况：宽大于前一个信封的宽或者等于前面的一个宽。
二分法来替换的目的是：List集合的数据是加进来信封的高的升序，同时宽也是升序的。当即将进来的信封高小于或者等于前一个的高，于是在List集合找到它的位置保存下来，相当于说，每次加入信封时，我们必须保证List集合的数据是按照升序排序的，这样才能保证更多的加入信封。
而这里为什么要按照高的降序排序呢？这是为了简便当即将进来的高比前一个的高大的话，这里只有一种可能，如果按照升序排序的话，还要考虑到宽等于的情况。
public static int maxEnvelopes(int[][] envelopes) {
if (envelopes == null || envelopes.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]; // ascending order
} else {
return b[1] - a[1]; // descending order
}
}
});
ArrayList<Integer> list = new ArrayList<Integer>();
//遍历每个信封，相当于决定每个信封的位置
for (int i = 0; i < envelopes.length; i++) {
if (list.size() == 0 || list.get(list.size() - 1) < envelopes[i][1]) {
list.add(envelopes[i][1]);
continue;
}
//二分替换，使得加进来的每个信封的宽在List集合中是升序排序
int l = 0;
int r = list.size() - 1;
while (l < r) {
int m = (l + r) / 2;
if (list.get(m) < envelopes[i][1]) {
l = m + 1;
} else {
r = m;
}
}
list.set(r, envelopes[i][1]);
}
return list.size();
}
