0354. Russian Doll Envelopes ============================ 题目信息 -------- :题号: 0354 :难度: Hard :主题: 二维嵌套、严格比较、数组、最大链长度 :原题: `LeetCode 0354 `_ :重点: 宽度和高度都必须严格变大、信封不能旋转、每个信封最多使用一次、只返回最大数量 题目重述 -------- 给定若干信封,``envelopes[i] = [wi, hi]`` 表示第 ``i`` 个信封的宽度和高度。一个信封只有在宽度和高度都严格小于另一个信封时,才能放入后者;任一维度相等都不能嵌套,信封也不能旋转。 返回能够形成的最长连续嵌套链所包含的信封数量。每个输入信封最多使用一次。信封数量位于 ``[1, 10^5]``,宽度和高度均位于 ``[1, 10^5]``。题目只要求返回最大数量,不要求恢复具体嵌套顺序。 自建示例 -------- 同宽信封不能互相嵌套: .. code-block:: text 输入:envelopes = [[2,2],[3,3],[3,5],[4,6]] 输出:3 解释:可以选择 [2,2] -> [3,3] -> [4,6],或 [2,2] -> [3,5] -> [4,6];两个宽度同为 3 的信封不能放入彼此。 只有高度增加仍不合法: .. code-block:: text 输入:envelopes = [[5,2],[5,7]] 输出:1 解释:两者宽度相等,不满足宽和高都严格增大的条件,因此最多选择一个。 用排序处理宽度,再在高度上做严格 LIS -------------------------------------- 先按宽度升序排序;宽度相等时按高度降序排序。这样在高度序列中寻找严格递增子序列时,同宽信封的高度会反向排列,不可能被同一条递增子序列同时选中,正好排除了“宽度相等也嵌套”的错误。宽度严格增加的候选则按高度的严格递增关系形成合法链。 维护 ``tails[len - 1]`` 为长度为 ``len`` 的递增子序列能够拥有的最小末尾高度。对当前高度用 ``lower_bound`` 找到第一个大于等于它的位置并替换;找不到时扩展序列长度。这里必须使用 ``lower_bound``,因为高度相等也不允许嵌套。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int maxEnvelopes(std::vector>& envelopes) { std::sort(envelopes.begin(), envelopes.end(), [](const std::vector& first, const std::vector& second) { if (first[0] != second[0]) { return first[0] < second[0]; } return first[1] > second[1]; }); std::vector tails; for (const auto& envelope : envelopes) { auto it = std::lower_bound( tails.begin(), tails.end(), envelope[1]); if (it == tails.end()) { tails.push_back(envelope[1]); } else { *it = envelope[1]; } } return static_cast(tails.size()); } }; 代码分析 -------- 宽度升序、高度降序的排序规则把二维严格条件转成一维严格 LIS;``tails`` 只记录每种长度的最小末尾,不直接保存最终链,但长度保持正确。排序时间为 ``O(n log n)``,LIS 同样为 ``O(n log n)``,额外空间为 ``O(n)``。