2021/3/25 俄罗斯套娃信封问题

题目描述

描述转载自力扣《354. 俄罗斯套娃信封问题》
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。

示例1

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

示例2

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

解题思路

1. 这是一个线性动态规划的单串问题，这道题目是建立在求 LIS 长度的基础之上的。做这道题之前强烈建议先看一下我之前的文章《最长递增子序列》 里面的题。
2. 我们可以把每个信封的宽从小到大排列，找宽度的最长递增子序列。然后在宽度顺序不变的情况下再将高度进行一次排序，找最长递增子序列。看看是不是有什么眉目了？
   
3. 我们可以使用使用快排，先对宽度进行排序，再对高度进行排序，然后选出 LIS，但实际测试证明，即使是快排，这种做法也相当耗时，我们需要考虑另一种办法。
4. 我们使用 Java 的 Arrays.sort() 进行排序，宽度从小到大排序，如果宽度一样，高度从大到小排序。
   
   这样排序有个好处，就是从前往后，宽度必然是会越来越大的，而宽度相同时，高度又会越来越小，导致无法组成 LIS，这样就限制了宽度相同的信无法套在一起，然后我们就可以无视宽度，只考虑高度。而只考虑高度的情况下，我们只需要和《最长递增子序列》 中做同样的事情，求 LIS 长度即可。

Java代码实现

1. 快排法（不推荐，仅供参考）

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        int len = envelopes.length;
        // 宽度排序
        wSort(envelopes, 0, len - 1);
        // 高度排序
        hSort(envelopes);
        // 比较 i-1 个信封的宽高
        int max = 1;
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        for (int i = 1; i < len; ++i) {
            for (int j = 0; j < i; ++j) {
                if (isUnsuitable(envelopes, i, j)) continue;
                int cur = dp[j] + 1;
                if (dp[i] < cur) dp[i] = cur;
            }
            max = dp[i] > max ? dp[i] : max;
        }
        return max;
    }

    private boolean isUnsuitable(int[][] arr, int i, int j) {
        return arr[j][0] >= arr[i][0] || arr[j][1] >= arr[i][1];
    }

    private void wSort(int[][] arr, int left, int right) {
        sortHelper(arr, left, right, 0);
    }

    private void hSort(int[][] arr) {
        int left = 0, right = 0;
        while (right < arr.length) {
            while (right + 1 < arr.length && arr[right + 1][0] == arr[left][0]) ++right;
            sortHelper(arr, left, right, 1);
            ++right;
            left = right;
        }
    }

    private void sortHelper(int[][] arr, int left, int right, int cdn) {
        if (left < right) {
            int pivot = qSort(arr, left, right, cdn);
            sortHelper(arr, left, pivot - 1, cdn);
            sortHelper(arr, pivot + 1, right, cdn);
        }
    }

    private int qSort(int[][] arr, int left, int right, int cdn) {
        int[] pivot = arr[left];    // 中轴值
        while (left < right) {
            while (left < right && arr[right][cdn] >= pivot[cdn]) --right;
            if (left < right) arr[left++] = arr[right];
            while (left < right && arr[left][cdn] <= pivot[cdn]) ++left;
            if (left < right) arr[right--] = arr[left];
        }
        // 替换中轴
        arr[left] = pivot;
        return left;
    }
}

2. 推荐解法

import java.util.*;
public class Solution {
    public int maxLetters (int[][] letters) {
        // 宽度从小到大排序，宽度相同时高度从大到小排序
        Arrays.sort(letters, 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];
            }
        });

        // h 数组存储高度，抹去了宽度
        int[] h = new int[letters.length];
        // 存储以 h[i] 结尾的 LIS 长度
        int[] dp = new int[letters.length];
        // 假设最坏的情况是没有递增，所以 LIS 长度最长为 1
        Arrays.fill(dp, 1);
        for (int i = 0; i < h.length; ++i) {
            h[i] = letters[i][1];
        }

        // 记录最长 LIS 长度
        int max = 1;
        for (int i = 1; i < dp.length; ++i) {
            for (int j = 0; j < i; ++j) {
                // 以 h[i] 结尾的递增子序列， h[j] 必然要比 h[i] 小，否则跳过
                if (h[j] >= h[i]) continue;
                int temp = dp[j] + 1;
                if (dp[i] < temp) dp[i] = temp;
            }
            max = dp[i] > max ? dp[i] : max;
        }
        return max;
    }
}