题目描述

1.PNG
[leetcode354]https://leetcode.com/problems/russian-doll-envelopes/
[算法原型 最长递增子序列]http://www.jianshu.com/p/25cc707d9c56

方法一：O(n^2)

算法流程：

1. a小->大 a=a'，b大->小
2. 同最长递增子序列算法模型的法一，检测的时候需要检测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);
    }