Problème LeetCode : meilleur moment pour acheter et vendre des actions

J'ai récemment abordé un problème classique de LeetCode : "Meilleur moment pour acheter et vendre des actions". Ce problème vous demande de trouver le profit maximum que vous pouvez réaliser en achetant et en vendant une action une fois. Plongeons dans les différentes approches que j'ai explorées, ainsi que leurs complexités. Voici l'URL du problème :

LeetCode 121

Approche par force brute (complexité temporelle : O(n^2))

La solution la plus simple pourrait être de comparer chaque élément du tableau avec tous les éléments restants. Pour chaque prix, nous calculons le profit qu’il générerait s’il était vendu ultérieurement. Nous suivons ensuite le profit maximum rencontré. Cette approche souffre cependant d'une grande complexité temporelle et entraîne un dépassement du délai.

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {

    let max = 0;
    for (var i = 0; i  a) return b - a;
    else return 0;
}

Voici pourquoi : Nous comparons chaque élément avec n-1 autres éléments, ce qui donne n*(n-1)/2 comparaisons. Cela se traduit approximativement par une complexité temporelle O(n^2), ce qui devient inefficace pour les grands ensembles de données. Malheureusement, cette approche conduit souvent à une erreur « Délai dépassé » sur LeetCode.

Approche à deux pointeurs (complexité temporelle : O(n))

Pour améliorer l'efficacité, nous pouvons tirer parti du fait que nous achetons avant de vendre. Nous pouvons introduire deux indicateurs :

• acheter : indique le prix d'achat potentiel actuel.
• vendre : pointe vers le candidat au prix de vente.

L'idée est de parcourir le tableau des prix, en commençant par le troisième élément (puisque les deux premiers éléments sont utilisés pour l'achat et la vente). Nous vérifions en permanence si la différence entre le prix de vente (élément actuel) et le prix d'achat est supérieure au profit maximum actuel. Si c'est vrai, nous mettons à jour le profit maximum. Sinon, nous mettons à jour le pointeur d'achat vers l'élément actuel (potentiellement un prix d'achat inférieur) et avançons le pointeur de vente d'un pas.

Cette approche offre une amélioration significative de la complexité temporelle, atteignant O(n) car nous ne parcourons le tableau qu'une seule fois.

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    let maxProfit = 0;
    let buy = 0;
    let sell = 1;
    while (sell 



<p><img src="https://img.php.cn/upload/article/000/000/000/172284027594031.png" alt="Problème LeetCode : meilleur moment pour acheter et vendre des actions" loading="lazy"    style="max-width:90%"  style="max-width:90%"></p>

<h2>
  
  
  Approche gourmande (complexité temporelle : O(n)) avec exemple Python
</h2>

<p>Nous pouvons atteindre une complexité temporelle similaire avec une approche gourmande. La clé ici est de comprendre que le profit maximum ne peut être obtenu que si nous achetons à bas prix et vendons à un prix élevé.  Par conséquent, nous pouvons parcourir le tableau des prix et suivre le prix minimum rencontré jusqu’à présent. Cela représente le prix d'achat potentiel.</p>

<p>Voici une implémentation Python de l'approche gourmande :<br>
</p>

<pre class="brush:php;toolbar:false">class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0;
        min_buy = float('inf')
        for price in prices:
            min_buy = min(min_buy , price )
            max_profit =  max(max_profit, price-min_buy)
        return max_profit

Vous pouvez toujours en savoir plus sur où me trouver sur mon portfolio ici

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!