百亿私募笔试真题｜俄罗斯套娃信封：排序 +

前阵子刷到一道百亿私募的笔试真题，俄罗斯套娃信封。题目看着挺唬人，其实核心就一句：信封得宽和高都严格大一圈，才能往里塞。

最直白的解法是动态规划，但得双重循环，复杂度 O(n²)，数据一多就卡壳。想提速，得先给信封排个序：宽度从小到大，宽度一样的，高度从大到小。这么一弄，二维嵌套直接变成了一维的最长递增子序列问题。

为啥同宽时高度非得降序？因为同宽的信封根本塞不进彼此。要是升序排，算法就会误把它们算进递增序列；降序排，它们就不可能同时出现在结果里了。

接着求最长递增子序列，用贪心加二分查找优化到 O(n log n)。维护一个 tails 数组，存各长度子序列的最小结尾值。遇到新高度，就用二分找位置：能接在后面就追加，不能就替换掉第一个大于等于它的数。这里必须用 bisect_left，因为题目要求严格递增，遇到相等的得替换而不是硬加。

最后返回 tails 的长度就行。排序消一维、同宽降序排、二分求 LIS，三步走完。