子序列——穿上马甲的LIS（二）

LeetCode_354_RussianDollEnvelopes

题目分析：如标题。依据宽度排序后，就是高度的LIS问题，只是判断上升的条件变化了。还是两种解法来一遍。

解法一：直接dp

//变种的Lis 宽高都要更大 那么排序先 -- 宽高固定 认真读题~
public static int maxEnvelopes(int[][] envelopes) {
    List<Pair> list = new ArrayList<>();
    for (int[] envelope : envelopes)
        list.add(new Pair(envelope[0], envelope[1]));
    Collections.sort(list);
    int dp[] = new int[envelopes.length];
    Arrays.fill(dp, 1);
    int max = 0;
    for (int i = 0; i < list.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            if (list.get(i).first > list.get(j).second && list.get(i).second > list.get(j).second) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}

private static class Pair implements Comparable<Pair>{
    public int first;
    public int second;
    public Pair(int first, int second){
        this.first = first;
        this.second = second;
    }

    @Override
    public int compareTo(Pair o) {
        return this.first - o.first;
    }
}

解法二：dp + 二分

/**
 * 几处优化和细节
 * 1.原地排序
 * 2.排序用了个方法排除[0]相等的情况，一看就懂。
 * 3.宽度都排好序了，只用看高度，用300题的二分优化方式查找.
 * 4.300题同样的思路，换了个写法，你还认识吗。
 */
public static int maxEnvelopes2(int[][] envelopes) {
    if(envelopes == null || envelopes.length == 0
            || envelopes[0] == null || envelopes[0].length != 2)
        return 0;
    Arrays.sort(envelopes, new Comparator<int[]>(){
        public int compare(int[] args1, int[] args2) {
            if (args1[0] == args2[0])
                return args2[1] - args1[1];
            else
                return args1[0] - args2[0];
        }
    });
    int[] dp = new int[envelopes.length];
    int count = 0;
    for (int[] envelop : envelopes) {
        int i = 0, j = count;
        while (i < j) {
            int m = i + (j - i) / 2;
            if (dp[m] < envelop[1]) i = m + 1;
            else j = m;
        }
        dp[i] = envelop[1];
        if (i == count) ++count;
    }
    return count;
}