俄罗斯套娃信封题目

小雨粑粑2012

来历：知乎
写在前面

本篇文章源于牛客网在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暗示以arr结尾的最长递增子序列，初始化都为1(自己组成最长递增子序列)，即dp = 1, 这个的静态转移方程（递推式）为，j从0到i - 1，假如arr > arr[j], 这dp = max(dp, 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 = 1;
                for (int j = 0; j < i; j++) {
                        if (arr > arr[j]) {
                                dp = Math.max(dp, 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 > len) {
                        len = dp;
                        index = i;
                }
        }
        int[] lis = new int[len];
        lis[--len] = arr[index];
        for (int i = index; i >= 0; i--) {
                if (arr < arr[index] && dp == dp[index] - 1) {
                        lis[--len] = arr;
                        index = i;
                }
        }
        return lis;
}上面这类算法的最差情况下的算法复杂度是 O(n^{2})。下面先容一种优化的方式。
除了数组dp，即dp暗示以arr结尾的最长递增子序列长度。再引入一个数组ends，初始长度和arr相称。ends暗示长度为i + 1的一切递增子序列的最小结尾。
举个栗子：
arr: [3, 1, 2, 4, 3]
1. 当i = 0时， 明显dp[0] = 1，此时长度为1的最长递增子序列的最小结尾为3，由于前面还没有遍历到。即ends = 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时，用arr去ends前面有查找ends[j]恰好大于或即是arr的阿谁值并替换，假如没有，则在ends前面增加arr。这个查找可以利用二分查找进步效力。而对于dp的更新，只需检察数组ends数组里面arr及其左侧的长度，dp就即是ends里面arr的下标+1。
数组更新完成后，前面的算法都是一样的，dp里面的最大值即为最长递增子序列。
具体代码以下：
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 > ends[m]) {
                                l = m + 1;
                        } else {
                                r = m - 1;
                        }
                }
                right = Math.max(right, l);
                ends[l] = arr;
                dp = l + 1;
        }
        return dp;
}
这类方式的最坏情况的时候复杂度为 O(nlogn)。
处理了最长递增子序列的题目，那末这类情况根基就处理了，具体代码就不贴出来了。
针对情况Ⅱ
对于情况Ⅱ，我们首先像情况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 = new Dot(es[0], es[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.h > ends[m]) {
                                        l = m + 1;
                                } else {
                                        r = m - 1;
                                }
                        }
                        right = Math.max(right, l);
                        ends[l] = dots.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逆序排列。需要好好体味进修下。

接待大师交换和批评斧正！

原文地址：https://zhuanlan.zhihu.com/p/29978994
免责声明：本帖内容由机械人自动收集于互联网，如加害了您的权益，请联系我们【E-Mail:cb@yoyodoc.com】 我们会实时删除侵权内容，给您带来未便，深感歉意！

123457468

那怎样算出最长嵌套的序列尼？