Leetcode – Top Interview –. Meilleur moment pour acheter et vendre des actions

C'est un problème simple avec la description suivante :

Vous recevez un tableau de prix où prix[i] est le prix d'une action donnée le ième jour.

Vous souhaitez maximiser votre profit en choisissant un seul jour pour acheter une action et en choisissant un autre jour dans le futur pour vendre cette action.
Renvoyez le profit maximum que vous pouvez réaliser grâce à cette transaction. Si vous ne pouvez réaliser aucun profit, renvoyez 0.

Exemple 1 :

Entrée : prix = [7,1,5,3,6,4]
Sortie : 5

Explication : Achetez le jour 2 (prix = 1) et vendez le jour 5 (prix = 6), profit = 6-1 = 5.
Notez qu'acheter le jour 2 et vendre le jour 1 n'est pas autorisé car vous devez acheter avant de vendre.

Exemple 2 :

Entrée : prix = [7,6,4,3,1]
Sortie : 0

Explication : Dans ce cas, aucune transaction n'est effectuée et le profit max = 0.

Contraintes :

1 <= prix.longueur <= 105
0 <= prix[i] <= 104

Au début, vous penseriez à trier et à obtenir des nombres de plus en plus petits, mais il se pourrait qu'à partir du tableau, vous obteniez différentes plages ou nombres avant et après, cela ferait que la différence ne correspondrait pas à ce qui est attendu, alors oubliez le tri.

Une bonne façon de résoudre ce cas est de considérer le min et le max ainsi que la différence lors de l'itération du tableau. Si le minimum est inférieur à celui prévu, réinitialisez tout, sinon continuez et mettez à jour le maximum lorsqu'il est inférieur au maximum, et obtenez toujours la différence, pas seulement le maximum, sinon vous risquez d'échouer lorsque nous obtenons moins du minimum, mais pas un grand nombre maximum. .

class Solution {
    public int maxProfit(int[] prices) {

        int min = prices[0];
        int max = prices[0];
        int diff = 0;

        for(int i=1;i prices[i]){
                min = prices[i];
                max = prices[i];
            } else if (max < prices[i]) {
                max = prices[i];
            }

            if(diff < (max - min)) {
                diff = max - min;
            }
        }

        return diff;
    }
}






Durée d'exécution : 2 ms, plus rapide que 77,66 % des soumissions en ligne Java pour le meilleur moment pour acheter et vendre des actions.

Utilisation de la mémoire : 61,4 Mo, soit moins de 80,34 % des soumissions en ligne Java pour le meilleur moment pour acheter et vendre des actions.


Vous pouvez encore améliorer davantage en supprimant min et en utilisant uniquement max, mais la différence n'est pas grave, mais constitue néanmoins une amélioration des performances.

—

C'est ça ! S'il y a autre chose à discuter, n'hésitez pas à laisser un commentaire, si j'ai raté quelque chose, faites-le-moi savoir afin que je puisse mettre à jour en conséquence.

À la prochaine publication ! :)


          

            
        
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!