算法细节系列（7）：354. Russian Doll Envelopes

354. Russian Doll Envelopes

在做这道题之前，我们先来看一道它的简化版本300. Longest Increasing Subsequence，官网给出了两种解法，时间复杂度分别为O(n2)O(n^2)和O(nlogn)O(n \log n).

Longest Increasing Subsequence

Problems:

Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length. Your algorithm should run in O(n2) complexity. Follow up: Could you improve it to O(n log n) time complexity?

求最长递增子序列，一道dp题，简单判断下，如果给出数组[10,9,2,5,3]，那么它的最长序列长度为3，在这种基础情况下增加数组元素[10,9,2,5,3,7,101,18]，我们进一步得到最长序列长度为4。如果我们用dp表示的话，dp[i] = Math.max(dp[i],dp[j]+1)，代码如下：

public int lengthOfLIS(int[] nums) {

        if (nums.length == 0) return 0;

        int[] dp = new int[nums.length+1];
        int max = 0;
        for (int i = 0; i < nums.length; i++){
            dp[i] = 1;
            for (int j = 0; j < i; j ++){
                if (nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

注意if条件的判断，只有当满足数组元素递增情况下，我才更新dp，很容易理解。max只需要随着dp[i]更新就好了。

官网还提出提示了另外一种更高效的算法，它的时间复杂度为O(nlogn)O(n \log n)，那么它应该怎么做？其实，在上述做法当中，你能看到一些瑕疵，它的第一层循环是定位当前i元素，并与前i-1个元素比较，这有点像插入排序，而我们知道插入排序在定位到第i个元素时，前面的元素已经是有序的了，有一种做法可以加快我们的查找速度，二分！！！而像第一种解法，虽然做了同样的O(n2)O(n^2)次的比较，但它没有更新元素的顺序，所以它所隐含的有序状态并没有得到高效利用。

所以自然而然的想法就出来了，我们每当定位到当前元素时，就把当前元素放到它该去的位置，如[10,9]比较后，显然应该变成[9,10]，但这种状态由题目意思是非法的，所以砍掉[10],就有了[9]，而此时定位到2，又更新为[2],继续i定位到5时，变成了[2,5]，这种状态是合法的，所以有了最新最长递增序列，它的好处就很明显了，本身有序，所以当前元素i在搜索位置插入时，可以优化到logn\log n，接下来就重点关注如何二分了！

该问题就变成了，只有【后续的元素大于当前最后一个元素】时，就增加数组长度并插入到最后位置。其它的，当小于等于最后一个元素时快速定位到指定位置即可。我们只要抓住括号内这个关键点即可。

抽象一下，我们只需要找到最大的下标i,使得dp[i] < key即可，所以有如下代码：

    public int lengthOfLIS(int[] nums) {

        if(nums.length == 0) return 0;

        int[] dp = new int[nums.length];
        int len = 1;
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++){
            int index = binarySearch(dp, 0, len-1, nums[i]);
            dp[index + 1] = nums[i];
            if (index + 1 == len){
                len ++;
            }
        }

        return len;

    }

    //典型的一种二叉树应用，保证它的准确性
    private int binarySearch(int[] nums, int lf, int rt, int key){

        while (lf < rt){
            int mid = lf + (rt + 1 - lf) / 2;

            if(nums[mid] >= key){
                rt = mid - 1;
            }else{
                lf = mid;
            }
        }

        if (nums[lf] < key) return lf; 

        return -1;
    }

可以去调试它去理解它的过程，这里总结两点：

• 当前i元素，插入到[0,len-2]的位置上，你可以丢弃它不看。
• 当前i元素，插入到 len - 1 的位置上时，它是你当前最长递增子序列中的一个解。
• 当前i元素，插入到 len 的位置上时，长度被更新，可见 len - 1 位置上元素的重要性。

升级版

Problems:

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope. What is the maximum number of envelopes can you Russian doll? (put one inside other)

Example:

Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

如果理解了上面那道简化版，那么这道题自然不在话下，但仍需要注意一些细节。

    public int maxEnvelopes(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[] arr1, int[] arr2) {
                if (arr1[0] == arr2[0])
                    return arr2[1] - arr1[1];
                else
                    return arr1[0] - arr2[0];
            }
        });
        int dp[] = new int[envelopes.length];
        int len = 0;
        for (int[] envelope : envelopes) {
            int index = Arrays.binarySearch(dp, 0, len, envelope[1]);
            if (index < 0)
                index = -(index + 1);
            dp[index] = envelope[1];
            if (index == len)
                len++;
        }
        return len;
    }

此处，我们需要知道官方lib库中提供的binarySearch返回的index，如果能够找到对应的key，那么直接返回对应的下标，而当找不到当前元素时，它返回的是最大的index，使得nums[index] < key，返回-(index)-1，所以对应的 ＋1 取反即为我们要插入的地方。

还需要注意一个地方，即comparator的比较顺序，先比较宽度，把宽度小的放在前面，如果宽度相等，则把长度长的放在前面，这是关键！！！理由很简单，当宽度相同时，我们有理由取最大的长度，如果取最小，那么对后续的序列，会出现宽度相同，而长度大的也被放入到了dp中，这种情况并不符合。不过说实话，想到这并不容易。