Hard

题目描述

给你一个二维整数数组 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 <= envelopes.length <= 105
  • envelopes[i].length == 2
  • 1 <= wi, hi <= 105

解题思路

这道题是经典的二维最长递增子序列问题，可以转化为一维LIS问题求解。

核心思路：

  1. 排序策略：按宽度升序排列，宽度相同时按高度降序排列。这样可以确保宽度相同的信封不会被同时选择。

  2. 转化为LIS：排序后，问题转化为在高度数组中寻找最长递增子序列，因为：

    • 宽度已经有序，只需保证高度递增
    • 宽度相同时高度降序，避免了宽度相等但高度不同的信封被错误选择

  3. 优化解法：使用二分查找优化LIS算法，维护一个递增序列，对于每个新元素：

    • 如果大于序列末尾，直接添加
    • 否则用二分查找找到第一个大于等于它的位置并替换

时间复杂度分析：

  • 基础DP：O(n²)，适用于n≤1000
  • 二分优化：O(n log n)，适用于大规模数据（推荐）

由于题目数据规模达到10^5，必须使用二分优化的解法。

代码实现

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
        });
        
        vector<int> lis;
        for (const auto& envelope : envelopes) {
            int height = envelope[1];
            auto it = lower_bound(lis.begin(), lis.end(), height);
            if (it == lis.end()) {
                lis.push_back(height);
            } else {
                *it = height;
            }
        }
        
        return lis.size();
    }
};

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        
        lis = []
        for _, height in envelopes:
            left, right = 0, len(lis)
            while left < right:
                mid = (left + right) // 2
                if lis[mid] < height:
                    left = mid + 1
                else:
                    right = mid
            
            if left == len(lis):
                lis.append(height)
            else:
                lis[left] = height
        
        return len(lis)

public class Solution {
    public int MaxEnvelopes(int[][] envelopes) {
        Array.Sort(envelopes, (a, b) => a[0] == b[0] ? b[1].CompareTo(a[1]) : a[0].CompareTo(b[0]));
        
        List<int> lis = new List<int>();
        foreach (var envelope in envelopes) {
            int height = envelope[1];
            int index = BinarySearch(lis, height);
            if (index == lis.Count) {
                lis.Add(height);
            } else {
                lis[index] = height;
            }
        }
        
        return lis.Count;
    }
    
    private int BinarySearch(List<int> list, int target) {
        int left = 0, right = list.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

/**
 * @param {number[][]} envelopes
 * @return {number}
 */
var maxEnvelopes = function(envelopes) {
    envelopes.sort((a, b) => a[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
二分优化LISO(n log n)O(n)
基础DPO(n²)O(n)

说明：

  • 时间复杂度：排序需要 O(n log n)，LIS 算法需要 O(n log n)，总体为 O(n log n)
  • 空间复杂度：LIS 数组最多存储 n 个元素，为 O(n)

相关题目