LeetCode 面试题 17.08. 马戏团人塔

约 6 分钟
文章信息 8 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 程序员面试金典（第 6 版） 拼多多 快手
标签
数组 动态规划 排序 二分查找

题目描述

✅ 面试题 17.08. 马戏团人塔

image-20260928231502492

题意分析

每个人的身高与体重由两个数组的相同下标给出。叠塔时，上方的人必须同时更矮、更轻，求最多能选多少人；相同身高或相同体重都不能上下接续。

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

核心思路

[!blue]

从塔顶到塔底看，人选的身高和体重都要严格递增。先把每个人的两个属性配成一对，按身高升序排列，再从排序后的体重序列中寻找最长严格递增子序列，就能消去身高这一维的查找。

但身高升序只保证不下降，不能让同高的人被同时选中。因此同身高时必须按体重降序排列：这一组内部体重不会上升，任何严格递增子序列都最多选一个人。这样选出的序列必然身高、体重都严格递增；反过来，任何合法人塔的身高本就严格递增，排序后仍能按原来的上下顺序选出，所以这个转换不会丢失最优解。

对体重维护 tails[k]，表示已扫描人员中，长度为 k + 1 的严格递增子序列能够取得的最小末尾体重。同样的长度，末尾越轻，未来越容易接上更重的人，因此只保留最小结尾就足够。

tails 严格递增：一个更长的递增序列去掉末尾后，所得较短序列的末尾一定更小，而较短长度的最优尾值只会更小。有了这个顺序，就可以二分查找当前体重 w 应放的位置，即第一个 tails[pos] >= w 的下标。

若 pos > 0，前一项 tails[pos - 1] < w，可以在那条长度为 pos 的序列后接上当前人，得到长度为 pos + 1、末尾为 w 的新候选。用 w 替换原尾值会改善或保持同长度的结尾；若 pos 已越过所有有效尾值，就能把当前最长序列再延长一层。相同体重只会替换，不会增加长度。

最后返回 tails 的有效长度。各位置记录的是不同长度下的最优结尾，它们不一定来自同一条实际人选序列，但不影响长度计算。

解题步骤

  1. 配对同一个人的身高与体重，按身高升序、同高体重降序排序。
  2. 按顺序处理每个人的体重，在 tails 的有效区间内二分第一个不小于它的值。
  3. 找到位置就替换尾值；若位置在有效区间末尾，就追加新尾值并增加长度。
  4. 返回最终有效长度；输入为空时没有候选，结果为零。

代码实现

// 身高升序、同身高体重降序排序后，在体重上求严格递增的最长子序列。
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;
    }
}

import "sort"

// 身高升序、同身高体重降序排序后，在体重上求严格递增的最长子序列。
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+1))$，其中 n 为人数。排序和对每人体重进行二分均在这个上界内。
  • 空间复杂度：$O(n)$，用于配对数组与最小结尾表；原身高、体重数组不被修改。

关键点总结

[!green]

  • 身高升序消去一维，同高体重降序阻止非法的同高接续。
  • 同长度只保留更小的末尾，因为它给后续留下的选择不会更少。
  • 求严格递增序列，应找第一个大于等于当前体重的位置。

易错点总结

[!yellow]

  • 同高时体重也升序，会把同高的多个人错误地选进人塔。
  • 二分找第一个严格大于当前体重的位置，会让相同体重增加长度。
  • 身高、体重分别独立排序，会破坏每个人的属性对应关系。
  • tails 不是最终人选名单，不能直接把表内各项当作同一条真实人塔输出。

相似题目

题目 难度 关联与区别
354. 俄罗斯套娃信封问题 困难 身高与体重对应信封的两维，等高时体重降序后做严格LIS，避免把同高者同时选入。
面试题 08.13. 堆箱子 困难 箱子题有三维严格限制且累加高度，本题只有两维并最大化人数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/63470513
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！