Last Stone Weight

+10

Tienes un montón de piedras, y stones[i] es el peso de la piedra i. En cada ronda, toma las dos piedras más pesadas y golpéalas entre sí. Si pesan lo mismo, ambas se destruyen. Si no, la más ligera se destruye y la más pesada reduce su peso a la diferencia entre los dos pesos.

Escribe una función llamada lastStoneWeight que juegue rondas hasta que quede como máximo una piedra y devuelva el peso de esa piedra, o 0 si no queda ninguna.

Función

lastStoneWeight(stones: integer-array) → integer

stonesinteger-array: los pesos de las piedras en la pila
Devuelveinteger: el peso de la última piedra, o 0 si no queda ninguna

Restricciones

1 ≤ stones.length ≤ 10⁴
1 ≤ stones[i] ≤ 1000

Ejemplos

Entrada: stones = [3, 9, 4, 6, 2]
Salida: 0
Explicación: 9 y 6 dejan un 3, después 4 y 3 dejan un 1, después 3 y 2 dejan otro 1. Las dos piedras de peso 1 se destruyen mutuamente, así que no queda nada y la respuesta es 0.

Entrada: stones = [10, 4, 1]
Salida: 5
Explicación: 10 y 4 dejan un 6, y 6 y 1 dejan un 5. Queda una piedra, que pesa 5.

Entrada: stones = [8]
Salida: 8
Explicación: Una sola piedra no tiene con qué ser aplastada, así que su peso 8 es la respuesta.

+13 pruebas ocultas al enviar

Para ir más allá

The pesos son como máximo 1000. ¿Puedes usar ese límite para terminar en tiempo O(n + W), donde W es el peso más grande, sin un heap?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Las reglas son una simulación: no hay ninguna fórmula para avanzar directamente, así que juegas todas las rondas. En cada ronda necesitas las dos piedras más pesadas de una pila que cambia continuamente, porque una piedra hecha añicos puede volver más ligera. Volver a ordenar en cada ronda permite encontrarlas, pero cuesta O(n log n) por ronda. Un montículo máximo proporciona la piedra más pesada y recibe otra nueva en O(log n).

Ordena la pila en cada ronda

Correcto, pero no termina con las pruebas más grandes

Intuición

Sigue las reglas al pie de la letra. Ordena el montón para que las dos piedras más pesadas queden al final, sácalas y, si sus pesos son distintos, vuelve a poner la diferencia. Repite hasta que quede una piedra o ninguna.

La diferencia puede quedar en cualquier lugar del orden. En el primer ejemplo, 9 y 6 dejan un 3, que debe ir debajo del 4, así que vuelves a ordenar antes de la siguiente ronda para encontrar las dos nuevas piedras más pesadas.

Cada ronda elimina al menos una piedra, así que hay hasta n-1 rondas, cada una con una ordenación de hasta n piedras: O(n² log n). Con n = 10^4, eso supone unas 10^4 ordenaciones de hasta 10^4 números, al menos 5 × 10^7 pasos incluso cuando la ordenación detecta que la lista está casi ordenada, y varias veces esa cantidad cuando no lo hace. Eso es demasiado lento para las pruebas más grandes, mientras que el montículo de abajo solo necesita unos cientos de miles de pasos.

Algoritmo

Copia las piedras en una lista llamada pile.
Mientras la pila tenga más de una piedra, ordénala de menor a mayor.
Quita las dos últimas piedras, heaviest y second.
Si son diferentes, añade heaviest - second de nuevo a la pila.
Devuelve la piedra restante o 0 cuando la pila esté vacía.

def lastStoneWeight(stones):
    pile = list(stones)
    while len(pile) > 1:
        pile.sort()  # the two heaviest stones move to the end
        heaviest = pile.pop()
        second = pile.pop()
        if heaviest != second:
            pile.append(heaviest - second)
    return pile[0] if pile else 0

Montículo máximo

Intuición

En cada ronda solo necesitas las piedras más grandes, nunca el orden completo. Para eso se construye un montículo máximo: mantiene el valor más grande en la cima, y quitar el elemento de la cima o añadir un valor cuesta O(log n).

Pon todas las piedras en el montículo. En cada ronda, extrae dos veces para obtener las dos más pesadas. Si son diferentes, vuelve a insertar la diferencia; el montículo la mueve por sí solo a la posición correcta. Para [10, 4, 1], extraes 10 y 4 e insertas 6; después extraes 6 y 1 e insertas 5, y en el montículo solo queda 5.

Hay como máximo n-1 rondas, cada una con dos extracciones y como máximo una inserción, así que el tiempo es O(n log n) y el montículo usa O(n) de espacio. Algunos lenguajes incluyen un montículo: heapq de Python es un montículo mínimo, así que almacena pesos negados; Java tiene PriorityQueue, C++ priority_queue, Go container/heap, Rust BinaryHeap y PHP SplMaxHeap. En los demás lenguajes, la solución implementa su propio montículo en un arreglo: el padre del índice i está en (i-1)/2, y un valor nuevo sube mientras sea mayor que su padre.

Algoritmo

Pon cada piedra en un montículo máximo.
Mientras el montículo contenga más de una piedra, extrae la más pesada y después la segunda más pesada.
Si son diferentes, inserta heaviest - second.
Devuelve la cima del montículo o 0 si está vacío.

import heapq


def lastStoneWeight(stones):
    # heapq is a min-heap, so store negated weights: the smallest entry is the heaviest stone.
    heap = [-w for w in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        heaviest = -heapq.heappop(heap)
        second = -heapq.heappop(heap)
        if heaviest != second:
            heapq.heappush(heap, -(heaviest - second))
    return -heap[0] if heap else 0

Errores comunes y casos límite

La simulación es corta, así que los errores se esconden en los extremos y en el propio montículo.

Devolver la cima de una pila vacía. Cuando las dos últimas piedras tienen el mismo peso, no queda nada y la respuesta es 0.
Usar accidentalmente un montículo mínimo. heapq de Python y PriorityQueue de Java, por defecto, devuelven el valor más pequeño; niega los pesos o pasa un comparador inverso.
Olvidar volver a negar. Con heapq, ambos valores extraídos son negativos, así que la diferencia que insertas es -(heaviest - second).
Ordenar una vez al principio y recorrer la lista. La diferencia entre dos piedras puede ser menor que el peso de piedras que todavía no has tocado, así que el orden fijo deja de ser válido después de la primera ronda.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Last Stone Weight?

Con un montículo máximo, construir el montículo y jugar como máximo n-1 rondas de dos extracciones y una inserción lleva un tiempo de O(n log n) y un espacio de O(n). Ordenar toda la pila en cada ronda, en cambio, lleva O(n² log n).

¿Por qué usar un montículo para el problema Último peso de piedra?

En cada ronda se buscan los dos valores más grandes de una colección que cambia después de cada ronda. Un montículo responde a la pregunta «cuál es el valor más grande» y acepta un valor nuevo en O(log n), sin mantener ordenada toda la colección. Eso es exactamente lo que repite la simulación.

¿Se puede resolver Last Stone Weight sin un montículo?

Sí, porque los pesos son pequeños. Cuenta cuántas piedras hay de cada peso del 1 al 1000 y recorre los pesos desde el más pesado hacia abajo. Las piedras iguales se cancelan por pares, y una piedra nueva siempre es más ligera que la más pesada de las usadas para crearla, así que el recorrido solo avanza hacia abajo. Esto se ejecuta en tiempo O(n + W) para el peso máximo W.

¿Cambia la respuesta el orden en que se trituran los pesos iguales?

No. Cuando varias piedras comparten el mayor peso, las dos que elijas pesan lo mismo en cualquier caso, así que la pila después de la ronda contiene los mismos pesos. La respuesta depende únicamente de los pesos, por eso todas las soluciones correctas devuelven el mismo número.

Python

def lastStoneWeight(stones):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

stones = [3, 9, 4, 6, 2]

Esperado