Best Time to Buy and Sell Stock
On vous donne une liste prices, où prices[i] est le prix d’une action le jour i. Vous pouvez acheter une action un jour et la vendre un jour ultérieur. Retournez le profit maximal que vous pouvez réaliser, ou 0 si toutes les transactions possibles entraînent une perte.
Fonction
- pricesinteger-array
- le cours de l’action chaque jour, dans l’ordre
- Renvoieinteger
- le bénéfice maximal obtenu en achetant une fois puis en vendant plus tard, ou 0
Contraintes
1 ≤ prices.length ≤ 1050 ≤ prices[i] ≤ 104- Vous effectuez au maximum une transaction, et vous vendez un jour après l’achat.
Exemples
- Entrée
- prices = [7, 2, 5, 9, 1, 4]
- Sortie
- 7
- Explication
- Achetez le jour 1 à 2 et vendez le jour 3 à 9 pour un bénéfice de 7. Le prix le plus bas, 1 le jour 4, survient après le 9 ; la meilleure vente qui suit ne rapporte donc que 3.
- Entrée
- prices = [9, 7, 4, 3, 1]
- Sortie
- 0
- Explication
- Le prix baisse chaque jour, donc chaque vente serait inférieure au prix d’achat. Vous ne faites aucune transaction, et le profit est de 0.
Pour aller plus loin
Et si vous pouviez effectuer autant de transactions que vous le souhaitez, tout en ne détenant qu’une seule action à la fois au maximum ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
La vente a toujours lieu après l’achat. Choisis un jour de vente : quel jour d’achat permet de réaliser le plus de profit ?
Pour un jour de vente donné, le meilleur jour pour acheter est le jour le moins cher qui le précède. Vous n’avez pas besoin de rechercher ce jour à nouveau chaque fois si vous vous en souvenez pendant que vous avancez.
Parcourez les jours dans l’ordre et gardez deux nombres : le prix le plus bas jusqu’ici et le meilleur profit jusqu’ici. Chaque jour, comparez le prix du jour moins le prix le plus bas avec le meilleur profit, puis mettez à jour le prix le plus bas.
Solution
Vous devez acheter avant de vendre, donc la réponse n’est pas le prix le plus élevé moins le prix le plus bas. Pour chaque jour où vous pourriez vendre, le meilleur achat est celui du jour le moins cher qui le précède. En gardant en mémoire ce prix le plus bas à mesure que vous avancez, vous réduisez le problème à un seul parcours.
Essaie chaque paire d’achat et de vente
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Chaque transaction comprend un jour d’achat et un jour de vente ultérieur : essaie donc chaque paire et garde la plus grande différence. Commencer avec un profit maximal de 0 couvre le cas où l’on choisit de ne pas effectuer de transaction. Chaque transaction autorisée est vérifiée, donc la réponse est correcte.
Une liste de n prix contient environ n²/2 paires : 100 000 jours représentent environ 5 milliards de soustractions.
Algorithme
- Définis
bestà 0. - Parcours chaque jour d’achat
buy. - Pour chacun, parcours chaque jour de vente
sellqui vient après. - Calcule
prices[sell]moinsprices[buy], et stocke le résultat dansbests’il est plus grand. - Retourne
best.
def maxProfit(prices):
best = 0
n = len(prices)
for buy in range(n):
for sell in range(buy + 1, n):
best = max(best, prices[sell] - prices[buy])
return best
Un passage avec le prix le plus bas jusqu’à présent
Intuition
Fixe le jour de vente i. Le meilleur jour pour avoir acheté est le jour le moins cher jusqu’à i, donc la meilleure transaction se terminant le jour i rapporte prices[i] moins le prix le plus bas jusque-là. Chaque jour de vente est associé à son meilleur jour d’achat, donc le plus grand de ces profits est la réponse. Un jour où un nouveau minimum est atteint, le profit est de 0, comme si aucune transaction n’avait été effectuée.
Le parcours lit chaque prix une seule fois et conserve deux nombres, lowest et best : temps O(n) et espace O(1).
Algorithme
- Définissez
lowestcomme le premier prix etbestcomme 0. - Parcourez les prix dans l’ordre.
- Si le prix actuel est inférieur à
lowest, faites-en le nouveaulowest. - Calculez le prix actuel moins
lowest, et stockez le résultat dansbests’il est supérieur. - Retournez
best.
def maxProfit(prices):
lowest = prices[0]
best = 0
for price in prices:
if price < lowest:
lowest = price
elif price - lowest > best:
best = price - lowest
return best
Pièges et cas limites
- Renvoyer le prix le plus élevé moins le prix le plus bas. Dans
[7, 2, 5, 9, 1, 4], cela donne 8, mais le 1 vient après le 9. La réponse est 7. - Laisser la réponse devenir négative. Dans
[9, 7, 4, 3, 1], la meilleure différence est -1 ; initialisezbestà 0, et non à la première différence. - Initialiser
lowestà 0. Chaque profit est alors égal au prix lui-même, donc[9, 7, 4, 3, 1]renvoie 9. Initialisez-le au premier prix.
Questions fréquentes3
Quelle est la complexité temporelle de Best Time to Buy and Sell Stock ?
La solution en un seul passage prend un temps O(n) pour n jours, car elle lit chaque prix une fois, et utilise un espace supplémentaire O(1) : le prix le plus bas jusqu’ici et le meilleur profit. Essayer toutes les paires de jours prend un temps O(n²).
Pourquoi ne pas soustraire le prix le plus bas du prix le plus élevé ?
Le prix le plus bas peut survenir après le plus élevé, et vous devez acheter avant de vendre. Dans [7, 2, 5, 9, 1, 4], le 1 vient après le 9, donc la meilleure transaction autorisée consiste à acheter à 2 et à vendre à 9 pour un gain de 7.
« Is Best Time to Buy and Sell Stock » est-il un problème de programmation dynamique ?
Tu peux le lire de l’une ou l’autre manière. Le prix le plus bas jusqu’à présent est un petit état que tu mets à jour chaque jour : c’est le point de vue de la programmation dynamique. Associer chaque vente au jour précédent le moins cher, c’est le point de vue glouton. Les deux mènent au même code en un seul passage.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def maxProfit(prices):
# Écrivez le code iciTest #1
Test #2
Argument
prices = [7, 2, 5, 9, 1, 4]
Résultat attendu
7