java - 根据多个字段在一组用户定义的对象中查找 LIS

Question

破解编码面试(第 5 版):第 11 章，问题 7

问题:马戏团正在设计一种塔式表演，其中的人们站在彼此的肩膀上。出于实用和美观的原因，每个人都必须比他或她下面的人矮且轻。给定马戏团中每个人的高度和体重，编写一个方法来计算这样一座塔中的最大可能人数。

我的疑问:

• 在书中给出的解决方案中，文中明确提到了 对元素进行排序会使解决方案变得太微不足道，那么为什么 元素最初已在代码中排序？

If the elements do not need to stay in the same(relative) order, then we would simply sort the array. This makes the problem too trivial, so let's assume that the elements need to stay in the same relative order.

这是书中完成排序的代码(代码的前三行):

    ArrayList<HtWt> getIncreasingSequence(ArrayList<HtWt> items)    
    {     
       Collections.sort(items);    
        return longestIncreaingSequence(items);    
    }

Answer 1

建议的解决方案由 2 个步骤组成:

1. 按重量排序
2. 找到高度上最长的递增子序列

引用的句子与第一步无关，而是与第二步(找到最长递增子序列)相关，它解释了我们不能只对高度进行排序，因为我们不能改变它们的顺序，因为它们是已经按权重排序。

看一下这个有 5 个人参与的示例:

weights:  4   5   1   7   2 
heights:  6   3   5   4   1

第 1 步后的结果(按重量排序):

weights:  1   2   4   5   7 
heights:  5   1   6   3   4

现在，查看高度，我们可以看到最长的递增子序列是 1 3 4，这告诉我们解决方案由 3 人组成。为了获得这个结果，我们不能只按高度排序，因为它们已经按体重排序了......

... the elements need to stay in the same relative order.

所以我们需要使用最长递增子序列算法。