LeetCode 354 俄罗斯套娃信封问题

本题是一道常见的面试题，脱胎于经典的动态规划例题，考察了对动态规划的核心思想的灵活运用能力，核心思路在于如何合理地利用降维操作保证核心信息无损而去除干扰信息。

题目描述

原题链接如下： LeetCode 354 俄罗斯套娃信封问题

题目大意

给出一系列的信封大小，每个信封可以认为是一个矩形，只有一个信封矩形的两边宽和高严格小于另一个信封，才能把它们嵌套，求最多可以嵌套多少个信封。

输入与输出

示例输入为：

1
2

Intput:
envelops = [[5,4],[6,4],[6,7],[2,3]]

对应输出为：

1
2

Output:
3

解题思路

首先，考虑最直接的暴力解法：按照信封的宽和高都升序进行排序，遍历所有信封，包含每个信封为结尾的嵌套序列就可以向它之前反向遍历进行确定，只要有比他小的信封就一定可以放入它之中。显然，这个暴力方法是一个时间复杂度为 $O(n^{2})$ 的动态规划方法。 不难看出，本题极其类似“最长递增子序列”的变种题目，相应题解在 LeetCode 300 最长上升子序列 中有详细的分析。但是本题的暴力解法却难以直接引入已有的一维数组的解法。因为，常见的二维转一维的解法需要固定一个维度后再对另一个维度的信息进行单独求解，但是固定宽度后可能会有一系列等宽但不等长的矩形，它们相互之间绝不可能嵌套，对求解过程掺杂了干扰信息。 那么，我们不妨先假设有办法剔除相等宽度矩形的干扰信息，然后再思考剔除的方法。一旦把等宽的矩形剔除则剩余全部矩形的宽度必定严格递增排序，则可以在计算的时候忽略宽度，而剩余的高度信息显然就是一维数组的“最长递增子序列”问题，直接引用它的解法即可，关键在于保证嵌套序列之中不会有一系列等宽的矩形。实际常见的方法是在把信封按照宽度递增排序之后，再按照高度递减排序，然后对高度统一进行一维数组的“最长递增子序列”问题求解。这样，等宽的信封序列在转化为一维数组的时候必定是递减的，不会对最后的结果子序列产生影响，即一定不会引入一系列等宽矩形。而不等宽的矩形只需要按照一维数组的解法，忽略宽度相互比较高度即可，最后一维数组“最长递增子序列”问题解法和排序的时间复杂度一样，故算法的总体时间复杂度为 $O(n \cdot \log{(n)})$ 这样的降维处理非常典型，确保没有丢失宽度排序这一信息，又去除了等宽矩形之间的高度影响。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun maxEnvelopes(envelopes: Array<IntArray>): Int {
        envelopes.sortWith(compareBy<IntArray> { it[0] }.thenByDescending { it[1] })
        val tail = IntArray(envelopes.size)
        var cnt = 0
        for (i in envelopes.indices) {
            val t = envelopes[i][1]
            var idx = tail.binarySearch(t, 0, cnt)
            if (idx < 0) idx = -idx - 1
            tail[idx] = t
            if (idx == cnt) cnt++
        }
        return cnt
    }
}