Startup VO 面试真题解析：俄罗斯套娃信封问题（Maximum Number of Envelopes That Can Be Nested）

Given a list of envelopes [width, height], find the maximum number of envelopes that can be nested inside each other.

An envelope can go inside another only if both its width and height are strictly smaller. Envelopes cannot be rotated.

这道题的核心是先对信封按宽度升序排序，在宽度相同的情况下按高度降序排序，这样可以把二维嵌套关系转化为高度上的最长递增子序列（LIS）问题。由于不能旋转且必须同时满足宽和高都严格变小，排序规则非常关键；如果宽度相同却把高度也升序排列，会错误地把相同宽度的信封串进序列。最终可以用二分优化的 LIS 在 O(n log n) 时间内求出最多能嵌套多少个信封。