题目描述
1.PNG
[leetcode354]https://leetcode.com/problems/russian-doll-envelopes/
[算法原型 最长递增子序列]//www.greatytc.com/p/25cc707d9c56
方法一：O(n^2)
算法流程：
- a小->大 a=a'，b大->小
- 同最长递增子序列算法模型的法一，检测的时候需要检测b
算法原理：
a已经是从小到大排序了，任何一个满足条件的排序都是在我这个按照a排完之后来选。就相当于按照b来求最长递增子序列。这里需要注意的是，在a相等的时候，假如我也按照b从小到大来排序，那么我之后对b的处理是会出问题的，比如(3,2)(3,4)，这样在之后按照b来进行求解时，由于2小于4,所以(3,4)是能够放在(3,2)上的，但是这就出现了问题，因为3和3并没有满足大于关系。而假如我们把b从大到小排序，那么上述就变成(3,4)，(3,2)，那么就不会再产生这个问题。
算法代码：
public int maxEnvelopes(int[][] envelopes) {
if(envelopes==null||envelopes.length==0)
return 0;
Dot[] dots=new Dot[envelopes.length];
for(int i=0;i<envelopes.length;i++){
dots[i]=new Dot(envelopes[i][0],envelopes[i][1]);
}
Arrays.sort(dots,new MyComparator());
// for(int i=0;i<dots.length;i++)
// System.out.println(dots[i].b);
int[] h=new int[dots.length];
h[0]=1;
for(int i=1;i<dots.length;i++){
int max=0;
Dot cur=dots[i];
for(int j=0;j<i;j++){
if(dots[j].b<cur.b){
max=Math.max(max,h[j]);
}
}
h[i]=max+1;
}
int max=0;
for(int i=0;i<h.length;i++){
max=Math.max(max,h[i]);
}
return max;
}
class Dot{
int a;
int b;
public Dot(int a,int b){
this.a=a;
this.b=b;
}
}
class MyComparator implements Comparator<Dot>{
@Override
public int compare(Dot d1, Dot d2) {
if(d1.a<d2.a){
return -1;
}
else if(d1.a>d2.a){
return 1;
}
else{
if(d1.b<d2.b)
return 1;
else if(d1.b>d2.b)
return -1;
else
return 0;
}
}
方法二：O(nlog(n))
算法流程：
同方法一，也是首先a从小到大,a相等时b从大到小。
只不过之后采用最长递增子序列算法原型的解题方案二来优化代码。
算法原理：
见文首链接 算法原型 最长递增子序列 的方法二。
算法代码：
public int maxEnvelopes(int[][] envelopes) {
if(envelopes==null||envelopes.length==0)
return 0;
Dot[] dots=new Dot[envelopes.length];
for(int i=0;i<envelopes.length;i++){
dots[i]=new Dot(envelopes[i][0],envelopes[i][1]);
}
Arrays.sort(dots,new MyComparator());
int[] h=new int[dots.length];
h[0]=dots[0].b;
int max=0;
for(int i=1;i<dots.length;i++){
int val=dots[i].b;
if(val>h[max]){
h[++max]=val;
continue;
}
int pos=findFirstBigger(h,0,max,val);//注意是在h中找啊
h[pos]=val;
}
return max+1;
}
public int findFirstBigger(int[] h,int left,int right,int target){
if(left==right)
return left;
int mid=(left+right)/2;
if(h[mid]<target)
return findFirstBigger(h,mid+1,right,target);
return findFirstBigger(h,left,mid,target);
}
