【LeetCode】马戏团人塔 Java 题解

2022 年 6 月 07 日
本文字数：952 字
阅读完需：约 3 分钟

题目描述

有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。

示例：
输入：height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]输出：6解释：从上往下数，叠罗汉最多能叠 6 层：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/circus-tower-lcci著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是叠罗汉题目，题目很清晰，规则是*上面的人要比下面的人矮一点且轻一点**。题目分别给出了每个人的身高和体重。
这是一个综合问题，同时需要考虑身高和体重，相对复杂，我们可以先排序身高数组，然后在处理体重数组。排序的时候，可以使用自定义的 comparator 处理器比较。
完成比较后的身高数组，我们之后需要处理体重，此时问题就转换成了最长上升子序列问题。最长上升子序列是经典题目，解决方法可以是 DP，也可以是二分查找 + DP，如果你没有听过最长上升子序列，建议先去学会最长上升子序列解法。在解决这个题目能容易一点。具体实现代码如下：

通过代码

class Solution {    public int bestSeqAtIndex(int[] height, int[] weight) {        int len = height.length;        int[][] person = new int[len][2];        for (int i = 0; i < len; ++i)            person[i] = new int[]{height[i], weight[i]};
        Arrays.sort(person, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);        int[] dp = new int[len];        int res = 0;        for (int[] pair : person) {            int i = Arrays.binarySearch(dp, 0, res, pair[1]);            if (i < 0)                i = -(i + 1);            dp[i] = pair[1];            if (i == res)                ++res;        }        return res;    }}