俄罗斯套娃信封问题

写在前面

本篇文章源于牛客网在9月13号晚上左神（左程云）的直播内容，在这对里面的俄罗斯套娃信封问题做一个课后总结，也对这个思路及代码做一个梳理。

题目

题目在leetcode354上也有描述，也是Google面试题。下面我进行中文的描述：

见过俄罗斯套娃吗？如图所示，大的娃娃可以套在小的外面，这样就可以把多个娃娃套在一起。

俄罗斯套娃

现在有很多信封，每个信封有宽度和高度[w,h]，只有宽度和高度都比其他信封大的时候才能够套在别的信封的外面。那么最多多少个信封可以像俄罗斯套娃那样套在一起？

例子

给你信封
envelopes = [[5, 4], [6, 4], [6, 7], [2, 3]],
则最多可以向俄罗斯套娃那样套在一起的信封数为3。([2, 3] => [5, 4] => [6, 7]).

算法分析

首先我们从两种情况来讨论这个问题:

• w无重复值（即信封的宽度每个信封都不一样）
• w可以重复（即信封的宽度存在一样的，题目就是这种情况）

针对情况I

当每个信封的宽度和高度不一样时，我们可以对信封按照宽度从小到大进行排序，比如针对信封[[3,2],[2, 4],[4,3],[5, 6],[6,5]排序后变为
w: 2 -> 3 -> 4 -> 5 -> 6
h: 4 -> 2 -> 3 -> 6 -> 5

此时，因为信封的宽度w已经是从小到大排列了，要想信封可以套，这要求关于信封高度h的数组[4, 2, 3, 6, 5]是的子序列是递增的，且要求是最长的（题目要求的是最多的信封），所以可以转化为另一个问题：给定数组，求它的最长递增子序列（也称最长上升子序列）。关于这个问题在leetcode300有具体描述。

最长递增子序列

比如给的数组arr = [3, 1, 2, 5, 4, 6]。
得到的最长递增子序列长度为4，即[1, 2, 5, 6]或[1, 2, 4, 6]。
这个问题的解法是动态规划，给一个相同长度的数组dp，dp[i]表示以arr[i]结尾的最长递增子序列，初始化都为1(本身构成最长递增子序列)，即dp[i] = 1, 这个的动态转移方程（递推式）为，j从0到i - 1，如果arr[i] > arr[j], 这dp[i] = max(dp[i], dp[j] + 1)。
具体代码如下：

// 求最长递增子序列方法
public static int[] lis1(int[] arr) {
    if (arr == null || arr.length == 0) {
        return null;
    }
    int[] dp = getdp1(arr);
    return generateLIS(arr, dp);
}

// 动态规划
public static int[] getdp1(int[] arr) {
    int[] dp = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return dp;
}

// 返回一个最长递增子序列（由动态规划产生的dp数组）
public static int[] generateLIS(int[] arr, int[] dp) {
    int len = 0;
    int index = 0;
    for (int i = 0; i < dp.length; i++) {
        if (dp[i] > len) {
            len = dp[i];
            index = i;
        }
    }
    int[] lis = new int[len];
    lis[--len] = arr[index];
    for (int i = index; i >= 0; i--) {
        if (arr[i] < arr[index] && dp[i] == dp[index] - 1) {
            lis[--len] = arr[i];
            index = i;
        }
    }
    return lis;
}

上面这种算法的最差情况下的算法复杂度是

下面介绍一种优化的方式。

除了数组dp，即dp[i]表示以arr[i]结尾的最长递增子序列长度。再引入一个数组ends，初始长度和arr相等。ends[i]表示长度为i + 1的所有递增子序列的最小结尾。
举个栗子：
arr: [3, 1, 2, 4, 3]

1. 当i = 0时， 显然dp[0] = 1，此时长度为1的最长递增子序列的最小结尾为3，因为后面还没有遍历到。即ends[i] = 3；
2. 当i = 1时，显然dp[1] = 1，以1结尾的最长递增子序列为1，此时没有长度为2的最长递增子序列，只有长度为1的最长递增子序列，然后最小结尾已经改变，1此时是最长递增子序列长度为1的最小结尾。即此时end[0] = 1
3. 当i = 2时，显然dp[2] = 2， 此时有长度为2的最长递增子序列，且最小结尾为2，长度为1的最小结尾为1。
   ...
   ...

依次类推
最后结果:
ends: [1, 2, 3]
dp: [1, 1, 2, 3, 3]

总结下数组ends和dp的更新策略，当遍历到arr[i]时，用arr[i]去ends前面有查找ends[j]刚好大于或等于arr[i]的那个值并替换，如果没有，则在ends后面添加arr[i]。这个查找可以使用二分查找提高效率。而对于dp[i]的更新，只需查看数组ends数组里面arr[i]及其左边的长度，dp[i]就等于ends里面arr[i]的下标+1。

数组更新完成后，后面的算法都是一样的，dp[i]里面的最大值即为最长递增子序列。

具体代码如下：

public static int[] lis2(int[] arr) {
    if (arr == null || arr.length == 0) {
        return null;
    }
    int[] dp = getdp2(arr);
    return generateLIS(arr, dp);
}

public static int[] getdp2(int[] arr) {
    int[] dp = new int[arr.length];
    int[] ends = new int[arr.length];
    ends[0] = arr[0];
    dp[0] = 1;
    int right = 0;
    int l = 0;
    int r = 0;
    int m = 0;
    for (int i = 1; i < arr.length; i++) {
        l = 0;
        r = right;
        while (l <= r) {
            m = (l + r) / 2;
            if (arr[i] > ends[m]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        right = Math.max(right, l);
        ends[l] = arr[i];
        dp[i] = l + 1;
    }
    return dp;
}

这种方式的最坏情况的时间复杂度为

解决了最长递增子序列的问题，那么这种情况基本就解决了，具体代码就不贴出来了。

针对情况Ⅱ

对于情况Ⅱ，我们首先像情况I一样考虑，对信封的宽度w按从小到大排序，那么此时面临一个问题，对于相同宽度的信封的高h怎么进行排序，如果我们也按照从小到大排序，那么此时按照信封高求出来的最长递增子序列有可能存在宽度w相同的情况。
举个栗子：
当宽度w = 1时， 此时有3个信封，h = 2, 3, 4
当宽度w = 2时，此时有两个信封，h = 3, 6
按照上面的排序方式排序后，
w: 1 -> 1 -> 1 -> 2 -> 2
h: 2 -> 3 -> 4 -> 3 -> 6
此时数组h的最长递增子序列为[2, 3, 4, 6]显然不符合条件。所以这种排序方式是错误的。

那么正确的排序方式是什么样的呢，就是当w相同时，h逆序，从大到小排列，这样你可以想一下，针对h求出来的最长递增子序列不会存在w相等，而h递增的情况，因为w相同的时候，右边的数总是小于等于左边的数，不会出现在最长递增子序列里面。
还是上面那个栗子排序后：
w: 1 -> 1 -> 1 -> 2 -> 2
h: 4 -> 3 -> 2 -> 6 -> 3
此时数组h的最长递增子序列长度为2（[4, 6]或[3, 6]或者其他），即最多有两个信封可以套。
具体代码如下：

public class RussianDollEnvelopes {

    public static class Dot {
        public int w;
        public int h;

        public Dot(int weight, int hight) {
            w = weight;
            h = hight;
        }
    }

    public static class DotComparator implements Comparator<Dot> {
        @Override
        public int compare(Dot arg0, Dot arg1) {
            if (arg0.w != arg1.w) {
                return arg0.w - arg1.w;
            } else {
                return arg1.h - arg0.h;
            }
        }
    }

    public static int maxEnvelopes(int[][] es) {
        if (es == null || es.length == 0 || es[0] == null || es[0].length != 2) {
            return 0;
        }
        Dot[] dots = new Dot[es.length];
        for (int i = 0; i < es.length; i++) {
            dots[i] = new Dot(es[i][0], es[i][1]);
        }
        Arrays.sort(dots, new DotComparator());
        int[] ends = new int[es.length];
        ends[0] = dots[0].h;
        int right = 0;
        int l = 0;
        int r = 0;
        int m = 0;
        for (int i = 1; i < dots.length; i++) {
            l = 0;
            r = right;
            while (l <= r) {
                m = (l + r) / 2;
                if (dots[i].h > ends[m]) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            right = Math.max(right, l);
            ends[l] = dots[i].h;
        }
        return right + 1;
    }

    public static void main(String[] args) {
        int[][] test = { { 4, 3 }, { 1, 2 }, { 5, 7 }, { 5, 3 }, { 1, 1 }, { 4, 9 } };
        System.out.println(maxEnvelopes(test));
    }
}

至此，俄罗斯套娃信封问题就解决了。

总结一下

这个问题主要在两个地方，一个是最长递增子序列的优化，二是当信封宽度相同时，信封高度h逆序排列。需要好好体会学习下。

欢迎大家交流和批评指正！

更多文章请访问我的博客