高耸算法

Question

在《破解编码面试》第四版中，存在这样的问题：

马戏团正在设计一个塔楼套路，由站在一个人的肩膀上的人组成。出于实际和美学的原因，每个人都必须比其下方的人矮一些和矮一些。考虑到马戏团中每个人的身高和体重，编写一种方法来计算此类塔楼中的最大人数。

示例：输入（ht，wt）：（65，100）（70，150）（56，90）（75，190）（60，95）（68，110）

输出：最长的塔长为6，从上到下包括：（56，90）（60,95）（65,100）（68,110）（70,150）（75,190）

这是 书中的解决方案

步骤1首先按高度然后按重量对所有项目进行排序这意味着，如果所有高度都是唯一的，则将按其高度对项目进行排序。如果高度相同，则将按其重量对项目进行排序

步骤2找到包含增加的身高和增加的体重的最长序列。为此，我们：

a）从序列的开头开始当前，max_sequence为空

b）如果下一项的高度和重量不大于上一项的重量和重量，我们将此项目标记为“不适合”

c）如果找到的序列的项目多于“最大序列”，则变为“最大序列”

d）之后，从“不合适的项目”开始重复搜索，直到我们到达原始序列的末尾

我对它的解决方案有一些疑问。

Q1

我认为此解决方案是错误的。

例如

(3,2) (5,9) (6,7) (7,8)

显然，这(6,7)是一项不合适的项目，但是(7,8)呢？根据解决方案，它不是不适合的，因为它的h和w大于(6,7)，但是，由于(7,8)不适合，因此不能将其考虑到序列中(5,9)。

我对吗？

如果我是对的，那么解决方法是什么？

Q2

我相信，即使有上述解决方案的解决方案，该解决方案的样式也至少会导致O(n^2)，因为根据步骤2-d，它需要一次又一次地迭代。

那么有可能有一个O（nlogn）解决方案吗？

Answer 1

您可以使用动态编程解决问题。

按高度对剧团进行排序。为简单起见，假定所有高度h_i和权重w_j是不同的。因此，h_i是一个递增的序列。

我们计算一个序列T_i，其中T_i是一个塔，其中人i在最大大小的顶部。T_1就是{1}。我们可以从较早的T_j推导出后续的T_k
－找到最大的塔T_j，它可以承受k的重量（w_j <w_k）并在其上站k。

剧团中可能最大的塔就是T_i中最大的塔。

该算法花费O（n ** 2）时间，其中n是剧团的基数。