View Code
回归到本题的解法
import java.util.Arrays;import java.util.Comparator;/* * 题意：CackingCodingInterview上的叠罗汉问题，leetcode上的沙皇问题 * 将最长递增子序列扩展到了二维 *//* * solutions : 时间复杂度O(n+n*log(n)+n*log(n)) 也就是n*log(n) * 目标是将二维数组抽象成一维数组，再利用解最长递增子序列的解法来解决这个问题 * 首先我们需要将二维数组排序，排序策略是先按照array[i][0]排序，在array[i][0]相同的情况下，按照array[i][1]倒序排序 * 为了排序我们可将array抽象成一个类A，二元组的两个元素分别是这个类A的两个成员变量 * 将array转化为A的数组，给A自实现一个排序函数（按照上面的排序策略） * 接下来就转化为了最长递增子序列问题，将类A数组的h成员变量看作之前的一维数组就好了 */public class Leetcode354 { public int maxEnvelopes(int envelopes) { if (envelopes.length 2) return envelopes.length; A a = new A[envelopes.length]; for (int i = 0; i envelopes.length; i++) { a[i] = new A(envelopes[i][0],envelopes[i][1]); } Arrays.sort(a,new Comparator A { @Override public int compare(A a, A b) { if (a.w b.w) { return 1; } else if (a.w b.w) { return -1; } else { if (b.h a.h) { return 1; } else if (b.h a.h) { return -1; } else return 0; } } }); int maxLen = 0; int h = new int[envelopes.length]; h[0] = a[0].h; for (int i = 1; i envelopes.length; i++) { int pos = getPos(h, 0, maxLen – 1,a[i].h); if (pos == -1) { h[maxLen++] = a[i].h; } else h[pos] = a[i].h; } return maxLen; } public int getPos(int h, int left, int right, int num) { if (left = right) { int mid = left + (right – left) / 2; if (h[mid] = num) { int pos = getPos(h, left, mid – 1, num); if (pos == -1) return mid; return pos; } else { return getPos(h, mid + 1, right, num); } } return -1; } public static void main(String args){ Leetcode354 l = new Leetcode354; int envelopes = {{5,1},{6,4},{6,7},{2,3}}; l.maxEnvelopes(envelopes); } }class A { int w = 0; int h = 0; public A(int w, int h) { this.w = w; this.h = h; }}
