354. 俄罗斯套娃信封问题 - Kotlin 常规DP+二分DP

原题地址：https://leetcode.cn/problems/russian-doll-envelopes/description/

题解

思路一：常规DP - 最长递增子序列：

二维版本的最长递增子序列问题，可以先对原数组进行排序

优先按照宽度的升序排序，这样至少能保证正序遍历的时候可以忽视宽度带来的影响，这样就变成了按照高度的一维最长递增子序列问题了
对于宽度相同的情况，我们应当按照高度的降序排序，因为当宽度相同的情况下，信封之间是不能进行套娃的，因此我们在这个宽度的所有信封中只能选择一个信封。对高度降序排序可以保证我们在选择了该信封后，后面遍历到的所有宽度相同的信封，其高度都大于该信封，从而自动地避免了选择相同宽度的情况

排序完毕后进行两层遍历：

dp[i]代表第0至第i-1封信封最多能够套娃多少层
正序遍历dp数组中的每一个信封i，由于排序过，我们能保证能被信封i包含的信封必然出现在i的左侧，因此令j遍历0到i
对于j而言，如果满足j的高度低于i的高度，则说明j可以被放进信封i中，此时i的层数为j的层数+1
对于j遍历的所有情况取层数的最大值即可

注：降维实际上在这个做法中并没有实质上的作用，即便我们对高度也进行升序排序，也只需要在判断的时候同时判断宽度和高度是否满足条件即可，降维这一步主要是为了下面的二分做法铺垫

时间复杂度：O(N^2)（该复杂度下会TLE）

空间复杂度：O(N)

class Solution {
    fun maxEnvelopes(envelopes: Array<IntArray>): Int {
        val seq = IntArray(envelopes.size) { 1 }
        var max = Int.MIN_VALUE
        val cmp = Comparator { a: IntArray, b: IntArray -> if (a[0] != b[0]) a[0] - b[0] else a[1] - b[1] }
        envelopes.sortWith(cmp)
        for ((index, envelop) in envelopes.withIndex()) {
            for (i in 0 until index) {
                if (envelop[0] > envelopes[i][0] && envelop[1] > envelopes[i][1]) {
                    seq[index] = Math.max(seq[i] + 1, seq[index])
                }
            }
            max = Math.max(seq[index], max)
        }
        return max
    }
}

思路二：一维DP + 二分查找：

参照官方题解思路

思路一的问题在于每次遍历新的信封时，都需要再次遍历该信封之前的所有信封，当我们遇到[[1,1],[2,2],...,[9999,9999]]这种大数据时也会力不从心，问题在于我们能否在一层循环的情况下解决最长递增子序列的问题

我们记录一个数组lastOfSeq，定义lastOfSeq[i]的值为长度为i的子序列的末尾元素的最小值（这里其实有贪心的思想，优先选择高度更小的信封可以为后面的信封留出更多的可能性去装它），由于我们采用的是DP的算法，在我们计算长度为i的子序列时，必然是先算出了长度为i-1的子序列，因此可以直接用ArrayList这种数据结构进行存储

同时因为我们计算的是递增的子序列：对于lastOfSeq[i]，必然大于lastOfSeq[i-1]，因此可以保证整个List是递增的，并且记录的是一个递增的高度序列

这个序列其实代表了一个正相关的关系：有着越大高度的信封，可以装的层数就越大，在这个关系基础上，对于信封i，我们尽可能地寻找不大于i的高度的最高的信封，则该信封的层数即是对于信封i的最优解，这个层数正好对应的就是List中的索引

因此我们在正序遍历i时，对lastOfSeq进行二分查找，查找不大于i高度的最高信封j，此时对应的索引（j的层数）就是相对于i的最优解，即i的层数=j的层数+1，因为同一个层数有许多种情况，对于lastOfSeq，我们需要更新为所有情况中i最小的那个值，由于我们实现将数组按照相同宽度下高度降序排序，因此不需要比较直接进行更新即可。当i的高度大于lastOfSeq中的所有元素（即大于lastOfSeq[lastOfSeq.size-1]）时，则可以在所有信封的基础上再套一层，则直接lastOfSeq.add即可

时间复杂度：O(NlogN)

空间复杂度：O(N)

class Solution {
    fun maxEnvelopes(envelopes: Array<IntArray>): Int {
        val lastOfSeq = ArrayList<Int>()
        val cmp = Comparator { a: IntArray, b: IntArray -> if (a[0] != b[0]) a[0] - b[0] else b[1] - a[1] }
        envelopes.sortWith(cmp)

        for (envelop in envelopes) {
            if (lastOfSeq.size == 0 || envelop[1] > lastOfSeq.last()) {
                lastOfSeq.add(envelop[1])
            } else {
                lastOfSeq.set(binSearch(lastOfSeq, envelop[1]), envelop[1])
            }
        }
        return lastOfSeq.size
    }

    fun binSearch(f: List<Int>, target: Int): Int {
        var left = 0
        var right = f.size - 1
        var mid: Int

        while (left < right) {
            mid = (right - left) / 2 + left
            if (f[mid] < target) {
                left = mid + 1
            } else {
                right = mid
            }
        }
        return left
    }
}