问题描述
LeetCode 面试题 17.08. 马戏团人塔 (opens in a new tab)，难度中等。
有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。
示例 1
输入：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
题解
动态规划 + for 循环
参考300. 最长递增子序列 (opens in a new tab)，但是本题在测试数据大的情况下会超时。
Solution.java
public int bestSeqAtIndex(int[] height, int[] weight) {
int[] dp = new int[height.length + 1];
Arrays.fill(dp, 1);
int result = 0;
int[][] pairs = new int[height.length][2];
for (int i = 0; i < height.length; ++i) {
pairs[i][0] = height[i];
pairs[i][1] = weight[i];
}
// 身高升序，身高相同体重降序
Arrays.sort(pairs, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
for (int i = 1; i < height.length; ++i) {
for (int j = 0; j < i; ++j) {
if (pairs[i][0] > pairs[j][0] && pairs[i][1] > pairs[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
result = Math.max(dp[i], result);
}
return result;
}动态规划 + 二分查找
Solution.java
class Solution {
public int bestSeqAtIndex(int[] height, int[] weight) {
int[] dp = new int[height.length + 1];
Arrays.fill(dp, 1);
int[][] pairs = new int[height.length][2];
for (int i = 0; i < height.length; ++i) {
pairs[i][0] = height[i];
pairs[i][1] = weight[i];
}
// 身高升序，身高相同体重降序
Arrays.sort(pairs, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
int[] tails = new int[height.length];
int size = 0;
for (int[] pair : pairs) {
// 二分查找，i > 0 返回查询的索引，i < 0 返回
int i = Arrays.binarySearch(tails, 0, size, pair[1]);
// 如果i < 0，说明当前体重在tails中没有找到匹配项，那么-(i + 1)就是它应该被插入的位置。这一步确保了我们总是在正确的位置更新tails数组，以保持其递增性质。
if (i < 0) i = -(i + 1);
// 将当前体重pair[1]赋值给tails[i]，这一操作可能是插入一个新值（扩展了递增子序列的长度）或者是更新一个现有位置的值（找到了一个更小的末尾值，为未来的扩展做准备）。
tails[i] = pair[1];
// 如果i == size，意味着我们在tails的末尾添加了一个新的值，因此需要将size增加1，这表示我们找到了一个更长的递增子序列。
if (i == size) size++;
}
return size;
}
}扩展
-
如果
i >= 0：这意味着
binarySearch方法找到了pair[1]（当前人的体重）在tails数组中的确切位置，即pair[1]的值在数组tails中已存在，并且i就是这个值的索引。 -
如果
i < 0：这是更常见的情况，表示
pair[1]在tails数组中不存在。binarySearch方法返回的是-(insertion point + 1)，其中“插入点”是pair[1]如果要被插入到tails中应该放置的位置索引，以保持数组的排序。为什么是-(insertion point + 1)而不直接是插入点呢？这是为了区分查找成功（找到相应元素）和查找失败（元素不在数组中）的情况。通过这种方式，即使返回值是0或负数，我们也能理解方法的结果。