Prix ​​finaux avec une remise spéciale dans un magasin

1475. Prix ​​finaux avec une remise spéciale dans un magasin

Difficulté :Facile

Sujets : Tableau, pile, pile monotone

Vous recevez un tableau de prix entiers où prix[i] est le prix du i^ème article dans une boutique.

Il y a une réduction spéciale sur les articles de la boutique. Si vous achetez le i^ème article, alors vous bénéficierez d'une remise équivalente aux prix[j] où j est l'indice minimum tel que j > i et prix[j] ≪= prix[i]. Sinon, vous ne bénéficierez d'aucune réduction.

Renvoyer une réponse de tableau entier où réponse[i] est le prix final que vous paierez pour le i^ème article de la boutique, compte tenu de la remise spéciale.

Exemple 1 :

• Entrée : prix = [8,4,6,2,3]
• Sortie : [4,2,4,2,3]
• Explication :
  • Pour l'article 0 avec prix[0]=8, vous bénéficierez d'une réduction équivalente aux prix[1]=4, donc le prix final que vous paierez est de 8 - 4 = 4.
  • Pour l'article 1 avec prix[1]=4, vous bénéficierez d'une remise équivalente aux prix[3]=2, donc le prix final que vous paierez est de 4 - 2 = 2.
  • Pour l'article 2 avec prix[2]=6, vous bénéficierez d'une remise équivalente aux prix[3]=2, donc le prix final que vous paierez est de 6 - 2 = 4.
  • Pour les articles 3 et 4, vous ne bénéficierez d'aucune réduction.

Exemple 2 :

• Entrée : prix = [1,2,3,4,5]
• Sortie : [1,2,3,4,5]
• Explication : Dans ce cas, pour tous les articles, vous ne bénéficierez d'aucune réduction.

Exemple 3 :

• Entrée : prix = [10,1,1,6]
• Sortie : [9,0,1,6]

Contraintes :

• 1 <= prix.longueur <= 500
• 1 <= prix[i] <= 1000

Indice :

1. Utilisez la force brute : Pour le ième article de la boutique avec une boucle trouvez la première position j satisfaisant les conditions et appliquez la remise, sinon, la remise est de 0.

Solution :

Nous devons appliquer une remise spéciale basée sur la condition qu'il existe un article ultérieur avec un prix inférieur ou égal au prix actuel, nous pouvons utiliser une approche par force brute. Nous allons parcourir le tableau des prix et, pour chaque article, rechercher le premier article avec un prix inférieur ou égal après lui. Ceci peut être réalisé avec des boucles imbriquées. Nous pouvons utiliser une pile pour suivre efficacement les prix des articles et appliquer la remise spéciale.

Approche:

1. Approche Stack :

   • Nous pouvons parcourir le tableau des prix de gauche à droite. Pour chaque article, nous utiliserons la pile pour suivre les prix qui n'ont pas encore trouvé de remise.
   • Pour chaque prix, nous vérifierons s'il est inférieur ou égal au prix en haut de la pile. Si tel est le cas, cela signifie que nous pouvons appliquer une réduction.
   • La pile stockera les indices des articles, et pour chaque article, nous vérifierons si le prix actuel est supérieur au prix à l'indice dans la pile, ce qui signifie qu'il n'y a pas de remise. Sinon, appliquez la remise en soustrayant le prix correspondant du prix actuel.

2. Edge Case : Si aucun article n'a un prix inférieur plus tard dans la gamme, aucune remise n'est appliquée.

Implémentons cette solution en PHP : 1475. Prix ​​finaux avec une remise spéciale dans un magasin

  
  
  Explication:




Initialisation :


Créez un tableau $result de la même taille que $prices et initialisez-le à 0.



Boucle extérieure :


Parcourez chaque prix à l'index $i pour calculer son prix final après remises.



Boucle intérieure :


Pour chaque prix $i, parcourez les prix suivants $j (où $j > $i).
Vérifiez si $prices[$j] ​​est inférieur ou égal à $prices[$i]. Si c'est vrai, définissez $discount = $prices[$j] ​​et quittez la boucle interne.



Calcul du prix final :


Soustrayez la remise trouvée de $prices[$i] et stockez le résultat dans $result[$i].



Résultat du retour :


Après avoir traité tous les prix, renvoyez le tableau de résultats final.





  
  
  Complexité:




Complexité temporelle : O(n²) (en raison des boucles imbriquées pour chaque prix).

Complexité spatiale : O(n) (pour le tableau de résultats).



  
  
  Exemples de résultats :



Pour les prix = [8, 4, 6, 2, 3], le résultat est [4, 2, 4, 2, 3].
Pour les prix = [1, 2, 3, 4, 5], le résultat est [1, 2, 3, 4, 5].
Pour les prix = [10, 1, 1, 6], le résultat est [9, 0, 1, 6].


Cette approche fonctionnera dans les contraintes du problème (1 <= prix.longueur <= 500), même si ce n'est pas la solution la plus optimisée.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :


LinkedIn
GitHub



          

            
  

            
        
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!