俄罗斯套娃信封问题 图解题解

俄罗斯套娃信封，这道题在挑什么

给一组信封，每项 [宽, 高]。一个要装进另一个，宽和高都得严格小于对方，有一边相等就套不进。问最多能套几层。题面 [[5,4],[6,4],[6,7],[2,3]]，[2,3] 塞进 [5,4]、[5,4] 塞进 [6,7]，套成 3 个。宽或高相等的彼此套不了，是全题的机关。

两两试套，为什么会慢到跑不完

n 个信封两两配对看能不能套只是 O(n²)，可真要穷举挑哪几个连成一串，每个选或不选分两条岔，2ⁿ 条组合枚举不完，还大半在重算同一段前缀。先把信封排好序、让谁能接谁有方向，指数枚举就收拢成一趟从左到右的递推（拿前面算好的结果往后推），开销靠这步压下来。

同宽的信封，为什么要按高从大到小排

排序规矩两条：宽从小到大，宽一样时高从大到小。第一条好懂：宽不减，套娃链才不回头。第二条才绕：宽相等的两个信封永远套不进彼此（宽得严格更小），可同宽若按高升序排，它俩的高一小一大、像能接上的递增对，求递增链时就被当成能套。改成高降序，同宽的高一路往下、绝不递增，链里最多挑一个，同宽误套被排序堵死。题面 [6,7]、[6,4] 同宽，排成先 7 后 4 正是这用意。

排完这列高度，套娃怎么就成了 LIS

排好序后宽已从小到大、不回头，只要在高上找一条严格变大的挑法，对应那串信封宽不减、高严格增，就能一个个套起来。二维套娃塌成一维：求高度序列的最长严格递增子序列（LIS，最长的一个个变大、可跳着挑的子序列）。

O(n log n) 的快法：开一个 lis 数组，存的不是真链，而是『各长度的递增链能达到的最小结尾』。每来一个高度 h，用二分（Python 的 bisect_left，对半砍找位置）在 lis 里找第一个不小于 h 的位置：落末尾说明 h 比所有结尾都大、能把最长链接长一节，链变长；落中间就用 h 替换那位置原值，把这档链结尾压小、日后更易接长。

拿题面那四个信封，亲手把 lis 填出来

拿题面 [[5,4],[6,4],[6,7],[2,3]] 走一遍。按『宽升、同宽高降』排成 [2,3]、[5,4]、[6,7]、[6,4]，抽出高度 [3,4,7,4]，lis 起初空。前三个 3、4、7 一个比一个大，二分都落末尾、依次接上成 [3,4,7]。最后的 4：找第一个不小于 4 的位置是 1（值正好 4），落中间，用 4 替换原来的 4，lis 仍 [3,4,7]、长度不变。走完长度 3，答案 3，即 [2,3] 套 [5,4] 套 [6,7]。

二分若改找第一个比 h 大的位置，答案为什么会偏大

二分若改成找『第一个比 h 大』，等高的高度会被接到链尾而非替换，两个等高信封就被当成能递增互套，答案凭空偏大——严格递增全靠『不小于』守住：等高触发替换、不接长。开销：排序 O(n log n)，每个高度一次二分、合计 O(n log n)，lis 最多装 n 个、空间 O(n)。两个边界：单个信封链长 1；题面 [[1,1],[1,1],[1,1]] 宽高全同，排完高度 [1,1,1]，只第一个接成 [1]、其余替换，答案 1。

Python

from typing import List
from bisect import bisect_left
class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        lis = []
        for _, h in envelopes:
            i = bisect_left(lis, h)
            if i == len(lis):
                lis.append(h)
            else:
                lis[i] = h
        return len(lis)

C++

#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), [](auto& a, auto& b){ return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0]; });
        vector<int> lis;
        for (auto &e : envelopes) {
            int h = e[1];
            auto it = lower_bound(lis.begin(), lis.end(), h);
            if (it == lis.end()) lis.push_back(h);
            else *it = h;
        }
        return lis.size();
    }
};

Java

import java.util.*;
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a,b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int[] lis = new int[envelopes.length];
        int size = 0;
        for (int[] e : envelopes) {
            int i = Arrays.binarySearch(lis, 0, size, e[1]);
            if (i < 0) i = -i - 1;
            lis[i] = e[1];
            if (i == size) size++;
        }
        return size;
    }
}