354. 俄罗斯套娃信封问题
题目描述
输入一个二维整数数组 envelopes，envelopes[i] = [w, h] 表示第 i 个信封的宽为 w、高为 h。
只有当信封 B 的宽和高都严格大于信封 A 时，A 才能装进 B。信封不能旋转。
从中挑出若干信封，让它们一个套一个。返回最多能套多少层，即这样一组信封的最大个数。
示例 1
输入：envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出：3
解释：可以 [2,3] 装进 [5,4]，再装进 [6,7]，共 3 个。
示例 2
输入：envelopes = [[1,1],[1,1],[1,1]] 输出：1
解释：三个信封大小相同，互相都装不进去，只能取 1 个。
数据范围
1 <= envelopes.length <= 10^5envelopes[i].length == 21 <= w, h <= 10^5
解题思路：排序 + 最长递增子序列（二分）
按宽升序排序，宽相同时按高降序。这样宽相同的信封高度递减，不可能同时出现在一个严格递增序列里。问题就变成对高度序列求最长严格递增子序列（LIS）。用 tails[k] 记录长度为 k+1 的递增子序列的最小结尾，对每个高度二分找第一个 >= h 的位置，替换或追加。
为什么正确
tails 严格递增；tails 的长度等于当前已处理序列的 LIS 长度。
复杂度分析
时间 O(n log n)，空间 O(n)。
易错点
宽相同时必须按高降序，否则 [6,4]、[6,7] 会被当成可嵌套；二分要找第一个 >= h 的位置（严格递增），而不是 > h。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
envelopes.sort(key=lambda e: (e[0], -e[1]))
tails = []
for _, h in envelopes:
lo, hi = 0, len(tails)
while lo < hi:
mid = (lo + hi) // 2
if tails[mid] < h:
lo = mid + 1
else:
hi = mid
if lo == len(tails):
tails.append(h)
else:
tails[lo] = h
return len(tails)class Solution {
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(b[1], a[1]));
int[] tails = new int[envelopes.length]; int size = 0;
for (int[] e : envelopes) {
int h = e[1];
int lo = 0, hi = size;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (tails[mid] < h)
lo = mid + 1;
else
hi = mid;
}
if (lo == size)
tails[size++] = h;
else
tails[lo] = h;
}
return size;
}
}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> tails;
for (auto& e : envelopes) {
int h = e[1];
int lo = 0, hi = tails.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (tails[mid] < h)
lo = mid + 1;
else
hi = mid;
}
if (lo == (int)tails.size())
tails.push_back(h);
else
tails[lo] = h;
}
return tails.size();
}
};func maxEnvelopes(envelopes [][]int) int {
sort.Slice(envelopes, func(a, b int) bool {
if envelopes[a][0] != envelopes[b][0] {
return envelopes[a][0] < envelopes[b][0]
}
return envelopes[a][1] > envelopes[b][1]
})
tails := []int{}
for _, e := range envelopes {
h := e[1]
lo, hi := 0, len(tails)
for lo < hi {
mid := (lo + hi) / 2
if tails[mid] < h {
lo = mid + 1
} else {
hi = mid
}
}
if lo == len(tails) {
tails = append(tails, h)
} else {
tails[lo] = h
}
}
return len(tails)
}var maxEnvelopes = function(envelopes) {
envelopes.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1]);
const tails = [];
for (const [, h] of envelopes) {
let lo = 0, hi = tails.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (tails[mid] < h)
lo = mid + 1;
else
hi = mid;
}
if (lo === tails.length)
tails.push(h);
else
tails[lo] = h;
}
return tails.length;
};function maxEnvelopes(envelopes: number[][]): number {
envelopes.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1]);
const tails: number[] = [];
for (const [, h] of envelopes) {
let lo = 0, hi = tails.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (tails[mid] < h)
lo = mid + 1;
else
hi = mid;
}
if (lo === tails.length)
tails.push(h);
else
tails[lo] = h;
}
return tails.length;
}其他解法
两种方法的排序和转化完全一致，区别在求最长递增子序列：动态规划对每个位置回看所有前驱，O(n²)；主解法维护各长度的最小结尾并二分查找，O(n log n)。
解法 2：排序 + 动态规划 时间 O(n²)，空间 O(n)
同样按宽度升序、宽度相同时高度降序排序，把问题变成高度序列的最长严格递增子序列。dp[i] 表示以第 i 个信封为最外层时最多能套几层：枚举所有 j < i 且高度更小的信封，dp[i] = max(dp[j]) + 1。答案是 dp 的最大值。
状态定义直观，容易理解为什么排序后可以转化为最长递增子序列。但 n 达到 10⁵ 时 O(n²) 会超时，只适合小数据或作为对拍基准。
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
envelopes.sort(key=lambda e: (e[0], -e[1]))
hs = [h for _, h in envelopes]
n = len(hs)
dp = [1] * n
for i in range(n):
hi = hs[i]
for j in range(i):
if hs[j] < hi and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
return max(dp)class Solution {
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(b[1], a[1]));
int n = envelopes.length, best = 0;
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++)
if (envelopes[j][1] < envelopes[i][1]) dp[i] = Math.max(dp[i], dp[j] + 1);
best = Math.max(best, dp[i]);
}
return best;
}
}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];
});
int n = envelopes.size(), best = 0;
vector<int> dp(n, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++)
if (envelopes[j][1] < envelopes[i][1]) dp[i] = max(dp[i], dp[j] + 1);
best = max(best, dp[i]);
}
return best;
}
};func maxEnvelopes(envelopes [][]int) int {
sort.Slice(envelopes, func(a, b int) bool {
if envelopes[a][0] != envelopes[b][0] {
return envelopes[a][0] < envelopes[b][0]
}
return envelopes[a][1] > envelopes[b][1]
})
n, best := len(envelopes), 0
dp := make([]int, n)
for i := 0; i < n; i++ {
dp[i] = 1
for j := 0; j < i; j++ {
if envelopes[j][1] < envelopes[i][1] {
dp[i] = max(dp[i], dp[j]+1)
}
}
best = max(best, dp[i])
}
return best
}var maxEnvelopes = function(envelopes) {
envelopes.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1]);
const n = envelopes.length;
const dp = new Array(n).fill(1);
let best = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++)
if (envelopes[j][1] < envelopes[i][1]) dp[i] = Math.max(dp[i], dp[j] + 1);
best = Math.max(best, dp[i]);
}
return best;
};function maxEnvelopes(envelopes: number[][]): number {
envelopes.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1]);
const n = envelopes.length;
const dp: number[] = new Array(n).fill(1);
let best = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++)
if (envelopes[j][1] < envelopes[i][1]) dp[i] = Math.max(dp[i], dp[j] + 1);
best = Math.max(best, dp[i]);
}
return best;
}