Vi essa pergunta no Careercup.com:

Dadas as alturas de n pessoas que estão em uma linha e uma lista de números correspondentes a cada pessoa (p), que fornece o número de pessoas que são mais altas que p e ficam de pé na frente de p. Por exemplo,

Alturas: 5 3 2 6 1 4

InFronts: 0 1 2 0 3 2

Significa que a atual ordem real é: 5 3 2 1 6 4

A questão obtém as duas listas de Heights e InFronts e deve gerar a ordem na fila.

Minha solução:

Isso poderia ser resolvido primeiro classificando a lista em ordem decrescente. Obviamente, para classificar, precisamos definir um objeto Person (com dois atributos de Height e InFront) e depois classificar as pessoas com base em sua altura. Então, eu usaria duas pilhas, uma pilha principal e uma pilha temporária, para montar a ordem.

Começando pelo mais alto, coloque-o na pilha principal. Se a próxima pessoa tiver um valor InFront maior que a pessoa no topo da pilha, isso significa que a nova pessoa deve ser adicionada antes da pessoa no topo. Portanto, precisamos remover pessoas da pilha principal, inserir a nova pessoa e, em seguida, retornar as pessoas que saíram da primeira etapa. Eu usaria uma pilha temporária para manter a ordem das pessoas que saíam. Mas quantos devem ser retirados? Como a lista está ordenada, precisamos mostrar exatamente o número de pessoas na frente da nova pessoa, ou seja, o InFront correspondente.

Eu acho que essa solução funciona. Mas a pior ordem seria O (n ^ 2) - quando colocar uma pessoa em seu lugar precisa aparecer todas as anteriores.

Existe alguma outra solução? possivelmente em O (n)?