Saltar al contenido

La fila de terracota

Enunciado

Mei, arqueóloga en Xi'an, sacó del foso una fila entera de guerreros de terracota para limpiarlos, y en el taller las figuras quedaron revueltas. Lo único que la salva es la etiqueta que le pegó a cada una al sacarla: cuántas figuras más altas que ella tenía delante en la fila.

Recibes alturas, una lista de enteros positivos, todos distintos (puede venir vacía), y delante, del mismo largo: delante[i] es cuántas figuras más altas que alturas[i] estaban antes que ella. Los datos siempre salen de una fila real, y con alturas distintas solo hay una fila que cumple todas las etiquetas. Regresa las alturas en el orden de esa fila, del frente hacia atrás. Sin figuras, regresa una lista vacía. Con [5, 3, 7, 6] y [1, 2, 0, 0] regresas [6, 5, 3, 7]. Revísalo: delante del 6 no hay nadie; delante del 5 está el 6, una más alta; delante del 3 están el 6 y el 5, dos más altas; delante del 7 están el 6, el 5 y el 3, pero ninguna es más alta. Las cuatro etiquetas cuadran.

Ejemplos

  • El ejemplo

    [5, 3, 7, 6], [1, 2, 0, 0] → [6, 5, 3, 7]

  • Siete guerreros

    [7, 4, 1, 2, 8, 9, 5], [1, 0, 6, 2, 1, 0, 2] → [4, 9, 2, 7, 5, 8, 1]

  • Nadie tenía una más alta delante

    [8, 4, 6, 2], [0, 0, 0, 0] → [2, 4, 6, 8]

  • De la más alta a la más baja

    [6, 2, 8, 4], [1, 3, 0, 2] → [8, 6, 4, 2]

  • Un solo guerrero

    [12], [0] → [12]

Además de estas, el reto tiene pruebas ocultas que se revelan al enviar tu solución.

Empiezas con esto

Python

def armar_fila(alturas, delante):
    pass

JavaScript

function armarFila(alturas, delante) {
}
Resolver este reto

Se abre en el navegador, con el editor y las pruebas. Este reto es del plan completo; los de O(1) y O(log n) son gratis.

Más retos de O(n²)

Ver todos los retos →