在Careercup.com上看到这个问题:
给定排在一条线上的n个人的高度和与每个人(p)相对应的数字列表,其给出高于p并站在p前面的人数.例如,
高度:5 3 2 6 1 4
InFronts:0 1 2 0 3 2
意味着实际的实际订单是:5 3 2 1 6 4
问题得到了两个高度和InFronts列表,并且应该生成排队的订单.
它可以通过首先按降序排序列表来解决.显然,要进行排序,我们需要定义一个对象Person(具有Height和InFront的两个属性),然后根据它们的高度对Persons进行排序.然后,我将使用两个堆栈,一个主堆栈和一个临时堆栈来构建订单.
从最高层开始,将它放在主堆栈中.如果下一个人的InFront值大于堆叠顶部的人,则意味着应该在最顶层的人之前添加新人.因此,我们需要从主堆栈中弹出人员,插入新人员,然后返回在第一步中弹出的人员.我会使用临时堆栈来保持弹出的人的顺序.但应该弹出多少？由于列表已排序,我们需要准确地弹出新人面前的人数,即相应的InFront.
我认为这个解决方案有效.但最糟糕的情况是O(n ^ 2) - 当一个人到位时需要弹出以前的所有.
还有其他解决方案吗？可能在O(n)？