英文原文
A circus is designing a tower routine consisting of people standing atop one another's shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.
Example:
Input: height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110] Output: 6 Explanation: The longest tower is length 6 and includes from top to bottom: (56,90), (60,95), (65,100), (68,110), (70,150), (75,190)
Note:
height.length == weight.length <= 10000
中文题目
有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。
示例：
输入：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)
提示：
height.length == weight.length <= 10000
通过代码
高赞题解
温馨提示：
题目要求是“矮一点 且 轻一点”，是严格要求<而不是<=。
自己可以用来小测的测试用例(答案为3而不是5)：
[1, 2, 2, 2, 3]
[4, 5, 6, 7, 8]思路
题目要求在2个维度上(即身高 + 体重)同时保持严格递增。
那么我们可以先将其中一个维度排好序，以保证在一个维度上保持递增（此时并非严格递增）；
之后就可以专注于处理另一个维度。
具体而言：
先根据身高 升序排序，若身高一样则根据体重 降序排序。
身高排序好之后，剩余待处理的就是体重。
处理体重的问题就是处理最长递增子序列的问题。
那么仔细想想为什么身高相同时，体重需要降序排序呢？
其实很简单的道理，将身高相同的人看成1个集合，若他们都按照体重升序来排序，则之后的二分法处理中，有一定的概率会在这集合中取 >= 2 个人作为最终结果。
为什么说是“有一定的概率会在这集合中取 >= 2 个人作为最终结果”呢？
比如:
身高:[1, 2, 2, 3, 4]
体重:[1, 3, 4, 5, 7]
显然，在身高升序排序，且身高相同则体重升序排序的预处理后，对体重进行二分查找得到的最长递增子序列的结果是[1, 3, 4, 5, 7]，而体重为3、4的那2个人身高相同，不符合题意。
比如:
身高:[1, 2, 2, 3, 4]
体重:[4, 1, 2, 5, 7]
显然，在身高升序排序，且身高相同则体重升序排序的预处理后，对体重进行二分查找得到的最长递增子序列的结果是[4, 5, 7]，这其中并没有包含身高为2的那2个人。(简单说就是运气好罢了，结果刚好符合题意)。
因为是体重升序，二分法处理时(从左往右遍历)，身高相同的人的集合 自己本身也有可能构成上升子序列，就使得最终答案内可能包含 身高相同，体重递增的结果。
同样，将身高相同的人看成1个集合，若他们都按照体重降序来排序，在二分法顺序遍历的过程中，是无法在这个集合中取 >= 2个人作为最终结果(即，要么取只能取1人，要么不取)。
因为是体重降序，二分法处理时(从左往右遍历)，身高相同的人的集合 自己本身是无法构成上升子序列，也就不会出现最终答案内包含 身高相同，体重递增的情况。
3种写法:
[-二分查找法(AC)]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; } }
[-记忆+DFS(超时/超内存)]class Solution { private int[][] person, memo; private int len; public int bestSeqAtIndex(int[] height, int[] weight) { len = height.length; 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]); memo = new int[len + 1][len]; for (int[] l : memo) Arrays.fill(l, -1); return dfs(-1, 0, 0); } private int dfs(int pre_idx, int cur_idx, int weight_bound) { if (cur_idx == len) return 0; if (memo[pre_idx + 1][cur_idx] >= 0) return memo[pre_idx + 1][cur_idx]; int taken = 0; if (pre_idx < 0 || person[cur_idx][1] > weight_bound) taken = 1 + dfs(cur_idx, cur_idx + 1, person[cur_idx][1]); int not_taken = dfs(pre_idx, cur_idx + 1, weight_bound); return memo[pre_idx + 1][cur_idx] = Math.max(taken, not_taken); } }
[-动态规划(超时)]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]; dp[0] = 1; int res = 1; for (int i = 1; i < len; ++i) { int max_val = 0, base_weight = person[i][1]; for (int j = 0; j < i; ++j) if (base_weight > person[j][1]) max_val = Math.max(max_val, dp[j]); dp[i] = max_val + 1; res = Math.max(res, dp[i]); } return res; } }
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 8693 | 31892 | 27.3% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
