Last Stone Weight

Q: Quelle est la complexité temporelle de Last Stone Weight ?

Avec un tas max, construire le tas et jouer au plus n-1 manches de deux extractions et d’une insertion prend un temps de O(n log n) et un espace de O(n) . Trier tout le tas à chaque manche prend plutôt O(n² log n) .

FacileTas

+10

Tu as un tas de pierres, et stones[i] est le poids de la pierre i. À chaque tour, prends les deux pierres les plus lourdes et fracasse-les ensemble. Si elles ont le même poids, elles sont toutes les deux détruites. Sinon, la plus légère est détruite et la plus lourde est réduite à la différence entre leurs deux poids.

Écris une fonction nommée lastStoneWeight qui joue des tours jusqu'à ce qu'il reste au plus une pierre, et renvoie le poids de cette pierre, ou 0 s'il ne reste aucune pierre.

Fonction

lastStoneWeight(stones: integer-array) → integer

stonesinteger-array: les poids des pierres dans le tas
Renvoieinteger: le poids de la dernière pierre, ou 0 s’il n’en reste aucune

Contraintes

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

Exemples

Entrée: stones = [3, 9, 4, 6, 2]
Sortie: 0
Explication: 9 et 6 laissent un 3, puis 4 et 3 laissent un 1, puis 3 et 2 laissent un autre 1. Les deux pierres de poids 1 se détruisent mutuellement, donc il ne reste rien et la réponse est 0.

Entrée: stones = [10, 4, 1]
Sortie: 5
Explication: 10 et 4 laissent un 6, et 6 et 1 laissent un 5. Il reste une pierre, pesant 5.

Entrée: stones = [8]
Sortie: 8
Explication: Une pierre seule n’a rien contre quoi être fracassée, donc son poids 8 est la réponse.

+13 tests cachés à la soumission

Pour aller plus loin

Les poids sont au plus égaux à 1000. Peux-tu utiliser cette borne pour terminer en O(n + W) temps, où W est le poids le plus élevé, sans tas ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Les règles décrivent une simulation : il n’existe pas de formule pour avancer directement, donc tu joues chaque manche. À chaque manche, il faut trouver les deux pierres les plus lourdes d’un tas qui change constamment, car une pierre brisée peut revenir plus légère. Trier à nouveau à chaque manche permet de les trouver, mais coûte O(n log n) par manche. Un tas max fournit la pierre la plus lourde et en récupère une nouvelle en O(log n).

Trier le tas à chaque tour

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Suivez les règles à la lettre. Triez le tas pour que les deux pierres les plus lourdes se trouvent à la fin, retirez-les et, si leurs poids diffèrent, remettez la différence. Répétez jusqu’à ce que le tas contienne une pierre ou aucune.

La différence peut se retrouver n’importe où dans l’ordre. Dans le premier exemple, 9 et 6 laissent un 3, qui doit se trouver avant le 4 ; il faut donc trier à nouveau avant le tour suivant pour trouver les deux nouvelles pierres les plus lourdes.

Chaque tour retire au moins une pierre ; il y a donc jusqu’à n-1 tours, chacun nécessitant un tri d’au plus n pierres : O(n² log n). Avec n = 10^4, cela représente environ 10^4 tris d’au plus 10^4 nombres, soit au moins 5 × 10^7 étapes même si le tri remarque que la liste est presque triée, et plusieurs fois plus s’il ne le remarque pas. C’est trop lent pour les tests les plus grands, tandis que le tas ci-dessous ne nécessite que quelques centaines de milliers d’étapes.

Algorithme

Copiez les pierres dans une liste appelée pile.
Tant que la pile contient plus d’une pierre, triez-la par ordre croissant.
Retirez les deux dernières pierres, heaviest et second.
Si elles sont différentes, ajoutez heaviest - second à la pile.
Renvoyez la pierre restante, ou 0 si la pile est vide.

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

Tas max

Intuition

À chaque tour, tu n’as besoin que des pierres les plus lourdes, jamais de l’ordre complet. Un tas max est conçu pour cela : il garde la plus grande valeur au sommet, et retirer le sommet ou ajouter une valeur coûte O(log n).

Place chaque pierre dans le tas. À chaque tour, retire deux éléments pour obtenir les deux plus lourdes. Si elles sont différentes, ajoute leur différence ; le tas la remet de lui-même à la bonne place. Pour [10, 4, 1], tu retires 10 et 4 et ajoutes 6, puis tu retires 6 et 1 et ajoutes 5, et le tas ne contient plus que 5.

Il y a au plus n-1 tours, chacun avec deux retraits et au plus un ajout ; le temps d’exécution est donc de O(n log n) et le tas utilise O(n) d’espace. Certains langages fournissent un tas : le heapq de Python est un tas min, donc il stocke les poids opposés ; Java possède PriorityQueue, C++ priority_queue, Go container/heap, Rust BinaryHeap et PHP SplMaxHeap. Dans les autres langages, la solution implémente son propre tas dans un tableau : le parent de l’indice i se trouve à (i-1)/2, et une nouvelle valeur remonte tant qu’elle est supérieure à son parent.

Algorithme

Placez chaque pierre dans un tas max.
Tant que le tas contient plus d’une pierre, retirez la plus lourde, puis la deuxième plus lourde.
Si elles sont différentes, ajoutez heaviest - second.
Renvoyez l’élément au sommet du tas, ou 0 s’il est vide.

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

Pièges et cas limites

La simulation est courte, donc les bugs se cachent dans les cas limites et dans le tas lui-même.

Renvoyer le sommet d’un tas vide. Lorsque les deux dernières pierres ont le même poids, il ne reste rien et la réponse est 0.
Utiliser accidentellement un tas min. heapq de Python et la PriorityQueue par défaut de Java renvoient la plus petite valeur ; nie les poids ou passe un comparateur inversé.
Oublier de revenir aux valeurs positives. Avec heapq, les deux valeurs extraites sont négatives, donc la différence que tu ajoutes est -(heaviest - second).
Trier une seule fois au début et parcourir la liste. La différence entre deux pierres peut être inférieure au poids de pierres que tu n’as pas encore touchées ; un ordre fixe devient donc obsolète après le premier tour.

Questions fréquentes4

Quelle est la complexité temporelle de Last Stone Weight ?

Avec un tas max, construire le tas et jouer au plus n-1 manches de deux extractions et d’une insertion prend un temps de O(n log n) et un espace de O(n). Trier tout le tas à chaque manche prend plutôt O(n² log n).

Pourquoi utiliser un tas pour Last Stone Weight ?

À chaque tour, il faut trouver les deux plus grandes valeurs d’une collection qui change après chaque tour. Un tas indique « quelle est la valeur la plus grande » et accepte une nouvelle valeur en O(log n), sans garder toute la collection triée. C’est exactement ce que répète la simulation.

Peut-on résoudre Last Stone Weight sans tas ?

Oui, car les poids sont faibles. Compte le nombre de pierres de chaque poids, de 1 à 1000, puis parcours-les en partant du poids le plus élevé. Les pierres de même poids s’annulent par paires, et une nouvelle pierre est toujours plus légère que la pierre la plus lourde utilisée pour la créer, donc le parcours ne fait que descendre. Cela s’exécute en O(n + W) pour le poids maximal W.

L’ordre dans lequel on écrase des poids égaux change-t-il la réponse ?

Non. Lorsque plusieurs pierres ont le poids le plus élevé, les deux que tu choisis pèsent la même chose dans les deux cas, donc le tas après le tour contient les mêmes poids. La réponse dépend uniquement des poids, c’est pourquoi toutes les solutions correctes renvoient le même nombre.

Python

def lastStoneWeight(stones):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

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

Attendu