LeetCode 面试题 17.08. 马戏团人塔

2025-03-26 HGNULB 约 12 分钟

文章信息 8 个分类 4 个标签

分类

LeetCode CodeTop 中等未解决 2-5 快手拼多多程序员面试金典（第 6 版）

题目描述

✅ 面试题 17.08. 马戏团人塔

题意分析

每个人有身高和体重两个属性，只有当一个人的身高与体重都严格大于另一个人时，才能站在其上面。要求选出尽可能多的人叠成一座塔，返回塔的最大层数。「都严格大于」意味着身高相同或体重相同的两个人绝不能同时入选，这一点是本题所有坑的源头。

「选出一个子集，使其在两个维度上同时严格递增」是一个二维偏序问题：任意两个人未必可比，比如 (170, 60) 与 (160, 70) 谁都压不住谁。二维偏序无法直接套一维的最长递增子序列，这是题目给出的最强算法信号——必须先想办法把其中一个维度「消灭」掉。

规模上人数可达五万量级，$O(n^2)$ 的朴素做法约二十五亿次操作会超时，这个约束直接排除了双重循环的 dp，逼着我们去找 $O(n \log n)$ 的做法。而「$n \log n$」这个量级本身就在暗示排序加二分。

边界上要注意：只有一个人时答案是 1；所有人身高完全相同时无论体重如何答案都是 1；数组本身无序，且 height 与 weight 是两个平行数组，必须先配对再排序，不能各自独立排序。

解法：排序 + 最长递增子序列

核心思路

最直接的做法是按身高排序后做 $O(n^2)$ 的 dp：dp[i] 表示以第 i 个人为塔顶时的最大层数，转移时枚举所有 j < i 且两维都严格小于的 j。正确但会超时，瓶颈在于「枚举前驱」这一步把 $O(n)$ 的扫描钉死在了每个位置上。

要提速就得回到二维偏序本身。观察一：把所有人按身高升序排序后，只要一个子序列在排序后的数组里满足「体重严格递增」，身高维度是不是就自动满足了？几乎是——身高已经非降，唯一的漏洞是身高相同的那些人，他们排在一起，若体重恰好递增就会被误认为可以叠起来，但身高相等违反了「严格大于」。

观察二：这个漏洞可以在排序规则里堵死。让身高相同的人按体重降序排列，那么同一身高组内的体重序列是递减的，任何一个严格递增的子序列都不可能同时取到组内两个人。于是排序之后，身高维度彻底退居幕后，问题化归为「在体重序列上求最长严格递增子序列」——一维 LIS。

由此写出算法的不变量：维护数组 tails，tails[k] 表示所有长度为 k+1 的严格递增子序列中，结尾元素的最小可能值；tails 在 [0, size) 上始终严格递增，size 即当前已知的 LIS 长度。这个「结尾尽可能小」的贪心之所以正确，是因为同样长度的子序列，结尾越小越容易被后续元素接上，不会丢掉任何最优解。

处理新体重 w 时，在 tails 里找第一个大于等于 w 的位置 lo（即 lower bound），把 tails[lo] 改写成 w。若 lo 等于 size，说明 w 比所有结尾都大，可以让 LIS 增长一位；否则是用更小的结尾替换掉同长度的旧记录，长度不变但为将来留出更多空间。取「大于等于」而非「大于」正是严格递增的要求：等于 w 的旧结尾必须被顶掉，不能让 w 接在它后面。

解题步骤

先把 height 与 weight 配对成二元组数组。两个平行数组各自排序会彻底打乱对应关系，把 A 的身高配到 B 的体重上，必须先绑定再整体排序。

排序规则写成「身高升序，身高相同则体重降序」。升序是为了让身高维度单调，降序是为了让同身高的人互相排斥。这两条缺一不可，也是本题与纯 LIS 的唯一区别。

用 tails 数组与计数器 size 维护贪心结构，而不是真的保存某条子序列。tails 里的元素通常并不构成一条真实存在的子序列，它只是每种长度的「最优结尾」的登记表；因为题目只要长度不要方案，这样就够了。

手写二分求 lower bound：循环条件 lo < hi，命中 tails[mid] < w 时 lo = mid + 1，否则 hi = mid。用 < 而不是 <= 做判据，保证等于 w 的位置会被 hi 收进来，最终 lo 停在第一个不小于 w 的下标。区间上界初值取 size 而非数组长度，因为 [size, n) 是尚未使用的脏数据。

写回 tails[lo] = w，并在 lo == size 时把 size 加一。两种情况用同一行赋值统一处理：追加时 lo 恰好是末尾的空位，替换时 lo 是已有位置，写法完全一致，不需要分支。

返回 size。它就是最长严格递增体重子序列的长度，也就是人塔的最大层数。

以 height = [1, 2, 2, 3, 4]、weight = [1, 5, 4, 2, 6] 走一遍。先配对得到 (1,1), (2,5), (2,4), (3,2), (4,6)，按规则排序后是 (1,1), (2,5), (2,4), (3,2), (4,6)——身高本就升序，两个身高 2 的人已经是体重 5 在前、4 在后的降序，顺序不变。取出体重序列 [1, 5, 4, 2, 6]。初始 size = 0。

w = 1：二分区间 [0, 0) 直接结束，lo = 0 == size，写入 tails[0] = 1，size 变为 1。tails = [1]。

w = 5：在 [1] 中找第一个不小于 5 的位置，tails[0] = 1 < 5 故 lo 推到 1，等于 size，写入 tails[1] = 5，size 变为 2。tails = [1, 5]。

w = 4：在 [1, 5] 中二分，mid = 0 时 1 < 4 故 lo = 1，mid = 1 时 5 < 4 不成立故 hi = 1，lo = 1 停下。lo ≠ size，执行替换 tails[1] = 4，size 仍为 2。tails = [1, 4]。含义是「长度为 2 的递增序列，结尾最小能做到 4」，比原来的 5 更有潜力。

w = 2：二分得 lo = 1（1 < 2 成立、4 < 2 不成立），替换 tails[1] = 2，size 仍为 2。tails = [1, 2]。注意这个 2 来自身高 3 的人，而 tails[0] = 1 来自身高 1 的人，恰好构成一条真实序列。

w = 6：1 < 6、2 < 6 均成立，lo 推到 2，等于 size，追加 tails[2] = 6，size 变为 3。tails = [1, 2, 6]。

最终返回 3。手工核对：取身高体重为 (1,1)、(3,2)、(4,6) 三人，身高 1 < 3 < 4、体重 1 < 2 < 6，两维都严格递增，能叠三层；想叠四层就必须用上两个身高为 2 的人之一再加其余三人，但 (2,5) 与 (2,4) 的体重都大于 (3,2)，接不上，所以 3 是上限。

再验证一下降序排序的必要性：若把身高相同的人按体重升序排，序列会变成 [1, 4, 5, 2, 6]，LIS 是 1, 4, 5, 6 长度为 4，多出来的那一层正是把 (2,4) 与 (2,5) 两个同身高的人同时算进去了，答案错误。

代码实现

// 身高升序、同身高体重降序排序后，在体重上求严格递增的最长子序列。
class Solution {
    public int bestSeqAtIndex(int[] height, int[] weight) {
        int n = height.length;
        int[][] people = new int[n][2];

        for (int i = 0; i < n; i++) {
            people[i][0] = height[i];
            people[i][1] = weight[i];
        }

        Arrays.sort(people, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }
            return b[1] - a[1];
        });

        int[] tails = new int[n];
        int size = 0;

        for (int[] person : people) {
            int w = person[1];
            int lo = 0;
            int hi = size;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (tails[mid] < w) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            tails[lo] = w;
            if (lo == size) {
                size++;
            }
        }

        return size;
    }
}

// 身高升序、同身高体重降序排序后，在体重上求严格递增的最长子序列。
func bestSeqAtIndex(height []int, weight []int) int {
    people := make([][2]int, len(height))
    for i := 0; i < len(height); i++ {
        people[i] = [2]int{height[i], weight[i]}
    }

    sort.Slice(people, func(i, j int) bool {
        if people[i][0] != people[j][0] {
            return people[i][0] < people[j][0]
        }
        return people[i][1] > people[j][1]
    })

    tails := make([]int, 0, len(people))
    for _, p := range people {
        w := p[1]
        lo, hi := 0, len(tails)
        for lo < hi {
            mid := (lo + hi) / 2
            if tails[mid] < w {
                lo = mid + 1
            } else {
                hi = mid
            }
        }
        if lo == len(tails) {
            tails = append(tails, w)
        } else {
            tails[lo] = w
        }
    }

    return len(tails)
}

复杂度分析

时间复杂度：$O(n \log n)$，其中 n 为人数。凭什么？配对是 $O(n)$；排序本身 $O(n \log n)$；主循环跑 n 轮，每轮在长度不超过 n 的 tails 上做一次二分，代价 $O(\log n)$，合计仍是 $O(n \log n)$。两段同阶相加不改变量级。

空间复杂度：$O(n)$。凭什么？配对数组 people 占 $O(n)$，tails 最长也是 n 个元素；排序的额外开销（Java 对象数组用归并、Go 用原地快排）不超过 $O(n)$。若允许原地修改输入还能省掉 people，但两个平行数组的题面决定了配对无法避免。

关键点总结

二维偏序的通用套路是「排序消一维，算法处理另一维」：先按维度 A 排序让它自动有序，再在维度 B 上跑一维算法。这个模式覆盖俄罗斯套娃、堆箱子、最长数对链等一大批题，是比记住本题更值钱的东西。

相等值的处理必须写进排序规则：只要题目说「严格大于」，第一维相等的元素就要让第二维逆序排列，用「组内不可能递增」来天然排斥同组元素。反之若题目允许「大于等于」，则第二维要升序。这条规则的方向完全由题面的严格性决定，不能凭感觉。

tails 不是一条真实的子序列：它是「每个长度的最小结尾」的登记表，中途可能出现 tails 里的元素来自不同分支的情况。理解这一点才能解释为什么可以随意替换中间元素而不影响长度的正确性，也才能回答「能否顺便输出方案」——不能，要输出方案得额外记录前驱。

严格递增用 lower bound、非严格递增用 upper bound：二分找的是「第一个 ≥ w」还是「第一个 > w」，一个字符之差就决定了相等元素能否接龙。写之前先把题目要的是严格还是非严格明确下来，再选二分变体。

hi 的初值是 size 而不是数组长度：tails 数组开满 n 但只有前 size 个有效，后面是未初始化的 0 或旧值，把它们纳入二分区间会得到完全错误的 lo。凡是「数组容量大于有效长度」的写法都要检查这一点。

面试视角：这题问的其实是「你会不会把 LIS 从一维推广到二维」。答完 $O(n \log n)$ 后主动补充两句会显著加分——一是「如果条件放宽成非严格大于，排序时同身高要改成体重升序、二分改成 upper bound」，二是「如果还要输出具体是哪些人，需要额外用一个数组记录每个人被放进 tails 时的下标与前驱，最后回溯」。另外可以指出这题与 354 俄罗斯套娃是同一道题的不同外衣。

易错点总结

错误写法：身高相同时体重也按升序排。用例 height = [1,2,2,3,4], weight = [1,5,4,2,6] → 体重序列变成 [1,4,5,2,6]，LIS 算出 4；正确答案是 3，多出的一层来自把身高同为 2 的 (2,4) 与 (2,5) 同时叠了上去，而他们身高相等根本压不住彼此。

错误写法：二分找 upper bound（判据写成 tails[mid] <= w）。用例 height = [1,2,3], weight = [5,5,5] → 三个 5 会被依次追加，返回 3；正确答案是 1，因为体重必须严格递增，三个体重相同的人只能选一个。严格递增必须用 lower bound。

错误写法：二分右边界初始化成 tails.length 而不是 size。用例 height = [1,2], weight = [9,10] → tails 数组长度为 2、初值全 0，处理 w = 9 时在 [0, 2) 上二分，tails[1] = 0 < 9 让 lo 落到 2，写入 tails[2] 直接越界抛异常。有效区间只有 [0, size)。

错误写法：height 与 weight 分别排序。用例 height = [2,1], weight = [1,9] → 各自排序后变成 height = [1,2]、weight = [1,9]，凭空造出一个 (1,1) 与 (2,9) 的组合返回 2；正确答案是 1，因为原始的两人是 (2,1) 与 (1,9)，互相都压不住。必须先配对再排序。

错误写法：比较器写成 a[0] - b[0] 但身高可能是大数导致溢出。本题身高体重都不超过一万，减法安全；但把这个模板照搬到取值接近 Integer.MAX_VALUE 的题目时，a[0] - b[0] 会溢出成负数让比较器违反传递性，Java 的 TimSort 会抛出 Comparison method violates its general contract!。稳妥写法是 Integer.compare(a[0], b[0])。

错误写法：追加时写 tails[size] = w 却忘了同时处理替换分支。用例 weight 排序后为 [3, 1] → w = 3 时 size 变 1，w = 1 时 lo = 0 ≠ size，若只在 lo == size 时写值，tails[0] 仍是 3，后续来一个 2 会被判为不能接续而错失更优结尾，长序列输入下答案偏小。替换与追加都要写值，只有 size 的自增才需要条件。

错误写法：Java 版最后返回 tails.length 而不是 size。用例 height = [1,2,3], weight = [3,2,1] → tails 数组一开始就按人数开满 3 个位置，但有效长度只有 1（体重递减，每次都是替换），返回 3；正确答案是 1。定长数组的容量与有效长度是两回事，Go 版因为用 append 动态增长才可以直接返回 len(tails)。

错误写法：以为排序后可以直接对身高做 LIS。用例 height = [1,1,1], weight = [1,2,3] → 身高序列排序后是 [1,1,1]，无论怎么做都得不到有意义的答案；真正需要跑 LIS 的是体重序列。身高的作用只是提供排序顺序，排完之后就不再参与计算。

错误写法：用 $O(n^2)$ 的 dp 版 LIS。用例是 n 取到五万的随机数据 → 双重循环约二十五亿次比较，必然超时。本题的数据范围就是冲着卡掉平方做法来的，必须上二分。

错误写法：Go 里把 people 声明成 [][]int 并在排序回调中比较错下标。用例 height = [1,2], weight = [2,1] → 若比较器误写成 people[i][1] < people[j][1]（按体重排序），排序结果变成 (2,1), (1,2)，体重序列 [1,2] 递增，返回 2；正确答案是 1。第一维必须是身高。

相似题目

题目	难度	考察点
300. 最长递增子序列	中等	纯一维 LIS，没有排序预处理这一步，是本题化归之后的裸模型
354. 俄罗斯套娃信封问题	困难	同为二维偏序，但输入本身就是二元组数组，无需配对，其余完全同构
面试题 08.13. 堆箱子	困难	三维偏序且要求最大高度和而非层数，排序只能消掉一维，剩下两维仍需 $O(n^2)$ dp
673. 最长递增子序列的个数	中等	除长度外还要统计方案数，`tails` 贪心不再够用，需要额外维护计数前缀
646. 最长数对链	中等	区间不重叠可按右端点贪心直接 $O(n \log n)$，不必绕道 LIS
1048. 最长字符串链	中等	前驱关系是「删一个字符」，无法排序成全序，只能按长度分层配合哈希转移