Russian Doll Envelopes
给一个2d数组,里面是一个信封的长宽,问多少个信封能套起来。
这个题和前几天的盒子那个题很想,就是最长连续递增子序列, 先要按照长度排序, 然后就知道从前到后的长度的信封都能放到前一个信封里,然后要考虑同样长度的信封, 这时候要按照从大到小排序, 即同样长的信封,如果宽度不一样, 那么可以构造成不同的递增子序列。另外答案的这个LIS是我跟leetcode学的写法。
class Solution {
private int lenOfLIS(int[] nums) {
int len = 0;
int[] dp = new int[nums.length];
for(int n : nums) {
int i = Arrays.binarySearch(dp, 0, len, n);
if(i < 0) {
i = -(i + 1);
}
dp[i] = n;
if(i == len)
len++;
}
return len;
}
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, (a,b) -> (a[0] == b[0] ? b[1] - a[1]: a[0] - b[0]));
int[] s = new int[envelopes.length];
for(int i = 0; i < envelopes.length; i++){
s[i] = envelopes[i][1];
}
return lenOfLIS(s);
}
}