俄罗斯套娃信封问题

记住「宽升高降排序 → 高度求严格 LIS → tails 二分(末尾 append、否则替换)」,下面逐步套它。

先排序。注意宽都为 6 的两个信封 [6,8] 排在 [6,7] 前面(高降序):这样它俩的高 8、7 在后面不会形成递增,避免把同宽的错当成能互套。

抽出排序后的高度序列 [3, 5, 8, 7, 4, 5]。问题已降成一维:在这串高度里找最长严格递增子序列的长度。

准备 tails 数组(初始空)。它不是真正的子序列,而是「每种长度的递增链所能达到的最小结尾」,用来给后续高度快速找接入点。

回到高度序列。前面 0 个已处理(蓝),现在看第 1 个高度 3(紫)。把它拿去更新 tails。

轮到高度 3。在 tails=[空] 里二分查第一个不小于 3 的位置,得到 i=0。

i 落在末尾,说明 3 能接到当前最长链后面,append。tails 变长,LIS 长度增到 1。

回到高度序列。前面 1 个已处理(蓝),现在看第 2 个高度 5(紫)。把它拿去更新 tails。

轮到高度 5。在 tails=[3] 里二分查第一个不小于 5 的位置,得到 i=1。

i 落在末尾,说明 5 能接到当前最长链后面,append。tails 变长,LIS 长度增到 2。

回到高度序列。前面 2 个已处理(蓝),现在看第 3 个高度 8(紫)。把它拿去更新 tails。

轮到高度 8。在 tails=[3, 5] 里二分查第一个不小于 8 的位置,得到 i=2。

i 落在末尾,说明 8 能接到当前最长链后面,append。tails 变长,LIS 长度增到 3。

回到高度序列。前面 3 个已处理(蓝),现在看第 4 个高度 7(紫)。把它拿去更新 tails。

轮到高度 7。在 tails=[3, 5, 8] 里二分查第一个不小于 7 的位置,得到 i=2。

i 在中间,用 7 替换 tails[2] 原来的 8:让长度 3 的链结尾更小,日后更容易接长。LIS 长度暂不变(仍 3)。

回到高度序列。前面 4 个已处理(蓝),现在看第 5 个高度 4(紫)。把它拿去更新 tails。

轮到高度 4。在 tails=[3, 5, 7] 里二分查第一个不小于 4 的位置,得到 i=1。

i 在中间,用 4 替换 tails[1] 原来的 5:让长度 2 的链结尾更小,日后更容易接长。LIS 长度暂不变(仍 3)。

回到高度序列。前面 5 个已处理(蓝),现在看第 6 个高度 5(紫)。把它拿去更新 tails。

轮到高度 5。在 tails=[3, 4, 7] 里二分查第一个不小于 5 的位置,得到 i=2。

i 在中间,用 5 替换 tails[2] 原来的 7:让长度 3 的链结尾更小,日后更容易接长。LIS 长度暂不变(仍 3)。

全部处理完,tails 长度 = 3,就是高度序列的最长严格递增子序列长度,也就是最多能套娃的信封数 3。注意 tails 本身的值 [3, 4, 5] 不一定是真实的那条链,但它的「长度」一定正确。

边界:单信封 1;全相同 1;同宽不同高也只 1。

两个延伸:排序把二维降一维;tails 二分把 LIS 从 O(n²) 提到 O(n log n)。