在基于多个字段

用户定义的对象的阵列查找LIS开裂编码面试（第5版）：CHP 11，QUES 7在基于多个字段

问题：马戏团正在设计的塔架例程包括人站在彼此的肩膀上。出于实际和美学的原因，每个人都必须比他或她下面的人短而轻。考虑到马戏团中每个人的身高和体重，请编写一种方法来计算这样一座塔楼中人数最多的人。

我的疑问：

在它在文本明确提到，排序的元素将会使溶液太微不足道，那么为什么元素已经在代码最初排序的书给出的解决方案？

如果元素并不需要留在同一个（相对）的命令，那么我们将在阵列只会排序。这使问题变得微不足道，因此让我们假设元素需要保持相同的相对秩序。

这里是从书其中排序已经完成（前三行的代码）的代码：

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

来源

2017-06-05 Gaurang Singhal

请给出一个比源代码缩写更具描述性的标题，每个问题限制自己一个问题。通过使用引用块来清楚引用哪些部分，并声明源（不是缩写，而不是标题）。 –

@MarkRotteveel完成 –

@MarkRotteveel请按照我提出的更改，删除downvote。 –

提出的解决方案是由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人组成。为了获得这个结果，我们不能仅仅根据高度进行排序，因为它们已经按照它们的重量排序了......

...元素需要保持相同的相对顺序。

因此，我们需要使用最长的递增子序列算法。

来源

2017-06-09 22:23:38

我不认为它意味着排序任何值，因为它会改变顺序的顺序。否则，在对任何一个属性进行排序之后，它就会成为LIS问题，如前所述，这些属性过于微不足道。 –

@GaurangSinghal引用的句子在关于LIS子问题的部分内，关于第2步。在本节中，有一个数组LIS的示例;引用的句子就是关于这个例子。然后解释说，在主要问题中应该使用与步骤2相同的方法，其中在按重量分类后，我们不能改变高度的顺序。是的，这个问题是关于LIS排序后的问题之一。 –

在再次阅读问题陈述和解决方案之后，看起来你是对的。尽管我解决了这个问题，但考虑到我们无法改变元素的顺序（甚至不是基于一个属性），使它变得更具挑战性。谢谢。 –

在基于多个字段

回答

相关问题