354 Russian Doll Envelopes
You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.
One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.
Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).
Note: You cannot rotate an envelope.
Example 1:
Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
Example 2:
Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1
首先对 envelopes 进行排序，按照 height 的升序排序，如果 height 相同，按照 width 的降序排序。这样问题就变成了 width 的最长递增子序列（Lonest Increasing Sequence）问题。因为 width 是降序排序的，当一个信封的 width 大于 一个它左边信封的 width ，同时它的 height 也是大于的。
求解最长递增子序列如果用传统的动态规划，是会超时的。
建立一个数组存放 width 的最长递增子序列，按顺序遍历所有信封，用二分查找找到当前信封可以插入数组中的位置，如果插入的是中间，更新中间该位置的 width ，如果插入的是右边，将其放入右边并把数组长度加一。最后得到的数组就是最长递增子序列，且长度就是答案。
时间复杂度 o(nlogn) ，空间复杂度 o(n)
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes,new Comparator<>(){
@Override
public int compare(int[] arr1, int[] arr2){
if(arr1[0]==arr2[0]){
return arr2[1]-arr1[1];
} else {
return arr1[0]-arr2[0];
}
}
});
/**
o(n^2), Time Limit Exceeded
int[] dp=new int[envelopes.length];
int max=1;
dp[0]=1;
for(int i=1;i<envelopes.length;++i){
dp[i]=1;
for(int j=0;j<i;++j){
if(dp[j]+1>dp[i] && envelopes[j][1]<envelopes[i][1]){
dp[i]=dp[j]+1;
}
}
if(dp[i]>max) max=dp[i];
}
return max;
*/
int[] lis=new int[envelopes.length];
int len=0;
for(int i=0;i<envelopes.length;++i){
int index=Arrays.binarySearch(lis,0,len,envelopes[i][1]);
if(index<0){
index=-index-1;
}
lis[index]=envelopes[i][1];
if(index==len){
len++;
}
}
return len;
}