Last Stone Weight

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

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

FácilMontículo

+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 haz que choquen entre sí. Si pesan lo mismo, ambas se destruyen. Si no, la más ligera se destruye y la más pesada se reduce a la diferencia entre sus pesos.

Escribe lastStoneWeight, que juega rondas hasta que quede como máximo una piedra y devuelve su peso, o 0 cuando no quede ninguna piedra.

Función

lastStoneWeight(stones: integer-array) → integer

stonesinteger-array: los pesos de las piedras del montón
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 1 se destruyen entre sí, así que 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, con un peso de 5.

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

Para ir más allá

Los 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 montículo?

Pistas

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

0 de 3 abiertas

Solución

No hay ninguna fórmula para saltar rondas: juegas todas las rondas. En cada ronda necesitas las dos piedras más pesadas de una pila que cambia constantemente, porque una piedra aplastada puede volver más ligera. Un montículo máximo entrega la piedra más pesada y vuelve a insertar una 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 literalmente: ordena el montón, saca las dos piedras más pesadas del final y vuelve a poner su diferencia si no es cero. Vuelve a ordenar en cada ronda, porque la diferencia puede quedar en cualquier lugar. En el primer ejemplo, 9 y 6 dejan un 3, que va debajo del 4.

En cada ronda se quita al menos una piedra, así que hay hasta n-1 rondas, y en cada una se ordenan hasta n piedras: O(n² log n). Para n = 10^4, eso equivale a unas 10^4 ordenaciones de hasta 10^4 números.

Algoritmo

Copia las piedras en una lista llamada pile.
Mientras la pila tenga más de una piedra, ordénala en orden creciente.
Quita las dos últimas piedras, heaviest y second.
Si son diferentes, vuelve a añadir heaviest - second 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

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 él. En cada ronda, extrae dos veces para obtener las dos piedras más pesadas y vuelve a insertar la diferencia si no es cero; el montículo la coloca en su sitio. Para [10, 4, 1], extraes 10 y 4 e insertas 6, después extraes 6 y 1 e insertas 5.

Hay como máximo n-1 rondas de dos extracciones y una inserción, así que el tiempo es O(n log n) y el espacio es O(n). En los lenguajes sin un montículo integrado, la solución mantiene uno en un arreglo, donde el padre del índice i está en (i-1)/2.

Algoritmo

Coloca 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 el elemento superior 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

Devolver la parte superior de una pila vacía. Cuando las dos últimas piedras pesan lo mismo, como en el primer ejemplo, no queda nada y la respuesta es 0.
Usar por accidente un montículo mínimo. heapq de Python y PriorityQueue predeterminada de Java devuelven el valor más pequeño; niega los pesos o pasa un comparador inverso.
Olvidar el signo al usar pesos negados. Ambos valores extraídos son negativos, así que el valor que hay que insertar es -(heaviest - second).
Ordenar una vez al principio y recorrer la lista. La diferencia puede ser menor que el peso de piedras que aún no has tocado, así que el orden queda obsoleto después de la primera ronda.

Preguntas frecuentes3

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

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

¿Por qué usar un heap para Last Stone Weight en lugar de una lista ordenada?

Una lista ordenada proporciona las dos piedras más pesadas a la vez, pero volver a ordenar la diferencia desplaza hasta n entradas, O(n²) en todas las rondas. Un montículo solo responde «cuál es el valor más grande» y acepta un valor nuevo, ambas operaciones en O(log n), que es todo lo que requiere la simulación.

¿Cambia la respuesta el orden en que se trituran las piedras de igual peso?

No. Cuando varias piedras tienen el mismo peso máximo, las dos que elijas pesan lo mismo en cualquier caso, así que la pila después de la ronda conserva los mismos pesos. La respuesta depende únicamente de los pesos.

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

Prueba #1

Prueba #2

Prueba #3

Argumento

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

Salida Esperada