題目描述
1.PNG
[leetcode354]https://leetcode.com/problems/russian-doll-envelopes/
[算法原型 最長遞增子序列]http://www.reibang.com/p/25cc707d9c56
方法一：O(n^2)
算法流程：
- a小->大 a=a'，b大->小
- 同最長遞增子序列算法模型的法一黄娘，檢測的時(shí)候需要檢測b
算法原理：
a已經(jīng)是從小到大排序了北戏，任何一個(gè)滿足條件的排序都是在我這個(gè)按照a排完之后來選尿赚。就相當(dāng)于按照b來求最長遞增子序列督惰。這里需要注意的是，在a相等的時(shí)候茴厉，假如我也按照b從小到大來排序泽台，那么我之后對b的處理是會出問題的，比如(3,2)(3,4)矾缓，這樣在之后按照b來進(jìn)行求解時(shí)怀酷，由于2小于4,所以(3,4)是能夠放在(3,2)上的，但是這就出現(xiàn)了問題嗜闻，因?yàn)?和3并沒有滿足大于關(guān)系蜕依。而假如我們把b從大到小排序，那么上述就變成(3,4)琉雳，(3,2)样眠，那么就不會再產(chǎn)生這個(gè)問題。
算法代碼：
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相等時(shí)b從大到小檐束。
只不過之后采用最長遞增子序列算法原型的解題方案二來優(yōu)化代碼。
算法原理：
見文首鏈接 算法原型 最長遞增子序列 的方法二束倍。
算法代碼：
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);
}
