Last Stone Weight

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

Avec un tas max, au plus n-1 tours de deux extractions et d’une insertion prennent un temps de O(n log n) et un espace de O(n) . Trier tout le tas à chaque tour prend 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 l’une contre l’autre. 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 voit son poids réduit de la différence entre les deux poids.

Écris lastStoneWeight, qui joue des tours jusqu’à ce qu’il ne reste au plus qu’une pierre et renvoie son poids, 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 1 se détruisent mutuellement, donc 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 seule pierre n’a rien contre quoi être écrasée, donc son poids 8 est la réponse.

Pour aller plus loin

Les poids sont au maximum de 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

Il n’existe pas de formule pour sauter des étapes : tu joues chaque manche. À chaque manche, il faut prendre les deux pierres les plus lourdes d’un tas qui change constamment, car une pierre écrasée peut revenir plus légère. 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 littéralement les règles : triez le tas, retirez les deux pierres les plus lourdes à l’extrémité, puis remettez leur différence si elle n’est pas nulle. Triez à nouveau à chaque tour, car la différence peut se retrouver n’importe où. Dans le premier exemple, 9 et 6 laissent un 3, qui se place sous le 4.

Chaque tour retire au moins une pierre, il y a donc jusqu’à n-1 tours, chacun triant jusqu’à n pierres : O(n² log n). Pour n = 10^4, cela représente environ 10^4 tris d’un maximum de 10^4 nombres.

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.
Retournez 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

Un tas max garde la plus grande valeur au sommet, et retirer l’élément du sommet ou ajouter une valeur coûte O(log n). Mets-y chaque pierre. À chaque tour, extrais deux fois pour récupérer les deux pierres les plus lourdes et réinsère la différence si elle n’est pas nulle ; le tas la remet à sa place. Pour [10, 4, 1], tu extrais 10 et 4, puis réinsères 6 ; ensuite, tu extrais 6 et 1, puis réinsères 5.

Il y a au plus n-1 tours de deux extractions et d’une réinsertion, donc le temps d’exécution est de O(n log n) et l’espace utilisé est de O(n). Dans les langages sans tas intégré, la solution en conserve un dans un tableau, l’indice du parent de l’indice i étant (i-1)/2.

Algorithme

Place chaque pierre dans un tas max.
Tant que le tas contient plus d’une pierre, retire la plus lourde, puis la deuxième plus lourde.
Si elles sont différentes, ajoute heaviest - second.
Renvoie le 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

Renvoyer le sommet d'un tas vide. Lorsque les deux dernières pierres ont le même poids, comme dans le premier exemple, il ne reste rien et la réponse est 0.
Utiliser accidentellement un tas min. heapq de Python et le PriorityQueue par défaut de Java renvoient la plus petite valeur ; inverse les poids ou passe un comparateur inversé.
Oublier le signe avec les poids négatifs. Les deux valeurs extraites sont négatives, donc la valeur à ajouter est -(heaviest - second).
Trier une fois au début et parcourir la liste. La différence peut être inférieure au poids de pierres que tu n'as pas encore touchées, donc l'ordre n'est plus valable après le premier tour.

Questions fréquentes3

Quelle est la complexité temporelle de Last Stone Weight ?

Avec un tas max, au plus n-1 tours de deux extractions et d’une insertion prennent un temps de O(n log n) et un espace de O(n). Trier tout le tas à chaque tour prend O(n² log n).

Pourquoi utiliser un tas pour Last Stone Weight plutôt qu’une liste triée ?

Une liste triée donne directement les deux pierres les plus lourdes, mais remettre leur différence en ordre décale jusqu’à n entrées, soit O(n²) sur l’ensemble des tours. Un tas répond uniquement à la question « quelle est la plus grande valeur ? » et accepte une nouvelle valeur, les deux en O(log n), ce qui suffit à la simulation.

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 tous les cas, donc le tas contient les mêmes poids après le tour. La réponse dépend uniquement des poids.

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

Test #1

Test #2

Test #3

Argument

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

Résultat attendu