Endgültige Preise mit Sonderrabatt in einem Geschäft

1475. Endgültige Preise mit Sonderrabatt in einem Geschäft

Schwierigkeit:Einfach

Themen: Array, Stack, Monotoner Stack

Sie erhalten ein ganzzahliges Array „Preise“, wobei „Preise[i]“ der Preis des i^tenArtikels in einem Geschäft ist.

Es gibt einen Sonderrabatt auf Artikel im Shop. Wenn Sie den i^ten Artikel kaufen, erhalten Sie einen Rabatt, der den Preisen[j] entspricht, wobei j der Mindestindex ist, sodass j > i und Preise[j] <= Preise[i]. Andernfalls erhalten Sie überhaupt keinen Rabatt.

Gibt eine Ganzzahl-Array-Antwort zurück, wobei Antwort[i] der Endpreis ist, den Sie für den i^tenArtikel im Shop zahlen, unter Berücksichtigung des Sonderrabatts.

Beispiel 1:

• Eingabe: Preise = [8,4,6,2,3]
• Ausgabe: [4,2,4,2,3]
• Erklärung:
  • Für Artikel 0 mit Preis[0]=8 erhalten Sie einen Rabatt entsprechend den Preisen[1]=4, daher beträgt der Endpreis, den Sie zahlen müssen, 8 - 4 = 4.
  • Für Artikel 1 mit Preis[1]=4 erhalten Sie einen Rabatt entsprechend den Preisen[3]=2, daher beträgt der Endpreis, den Sie zahlen müssen, 4 - 2 = 2.
  • Für Artikel 2 mit Preis[2]=6 erhalten Sie einen Rabatt in Höhe von Preisen[3]=2, daher beträgt der Endpreis, den Sie zahlen müssen, 6 - 2 = 4.
  • Für die Artikel 3 und 4 erhalten Sie überhaupt keinen Rabatt.

Beispiel 2:

• Eingabe: Preise = [1,2,3,4,5]
• Ausgabe: [1,2,3,4,5]
• Erklärung:In diesem Fall erhalten Sie für alle Artikel überhaupt keinen Rabatt.

Beispiel 3:

• Eingabe: Preise = [10,1,1,6]
• Ausgabe: [9,0,1,6]

Einschränkungen:

• 1 <= Preise.Länge <= 500
• 1 <= Preise[i] <= 1000

Hinweis:

1. Wenden Sie rohe Gewalt an: Suchen Sie für den i-ten Artikel im Shop mit einer Schleife die erste Position j, die die Bedingungen erfüllt, und wenden Sie den Rabatt an, andernfalls beträgt der Rabatt 0.

Lösung:

Wir müssen einen speziellen Rabatt gewähren, der auf der Bedingung basiert, dass es einen späteren Artikel mit einem Preis gibt, der kleiner oder gleich dem aktuellen Preis ist. Wir können einen Brute-Force-Ansatz verwenden. Wir durchlaufen das Preisarray und suchen für jeden Artikel nach dem ersten Artikel mit einem niedrigeren oder gleichen Preis danach. Dies kann mit verschachtelten Schleifen erreicht werden. Wir können einen Stapel verwenden, um die Preise der Artikel effizient zu verfolgen und den Sonderrabatt anzuwenden.

Ansatz:

1. Stack-Ansatz:

   • Wir können das Preisarray von links nach rechts durchlaufen. Für jeden Artikel verwenden wir den Stapel, um die Preise zu verfolgen, für die noch kein Rabatt gefunden wurde.
   • Für jeden Preis prüfen wir, ob er kleiner oder gleich dem Preis oben im Stapel ist. Wenn ja, bedeutet das, dass wir einen Rabatt gewähren können.
   • Der Stapel speichert die Indizes der Artikel und wir prüfen für jeden Artikel, ob der aktuelle Preis höher ist als der Preis am Index im Stapel, was bedeutet, dass es keinen Rabatt gibt. Andernfalls wenden Sie den Rabatt an, indem Sie den entsprechenden Preis vom aktuellen Preis abziehen.

2. Edge Case: Wenn später in der Reihe kein Artikel einen niedrigeren Preis hat, wird kein Rabatt gewährt.

Lassen Sie uns diese Lösung in PHP implementieren: 1475. Endgültige Preise mit Sonderrabatt in einem Geschäft

  
  
  Erläuterung:




Initialisierung:


Erstellen Sie ein Array $result mit der gleichen Größe wie $prices und initialisieren Sie es auf 0.



Äußere Schleife:


Durchlaufen Sie jeden Preis bei Index $i, um seinen Endpreis nach Rabatten zu berechnen.



Innere Schleife:


Iterieren Sie für jeden Preis $i die nachfolgenden Preise $j (wobei $j > $i).
Überprüfen Sie, ob $prices[$j] ​​kleiner oder gleich $prices[$i] ist. Wenn wahr, setzen Sie $discount = $prices[$j] ​​und verlassen Sie die innere Schleife.



Endgültige Preisberechnung:


Subtrahieren Sie den gefundenen Rabatt von $prices[$i] und speichern Sie das Ergebnis in $result[$i].



Ergebnis zurückgeben:


Nachdem alle Preise verarbeitet wurden, geben Sie das endgültige Ergebnisarray zurück.





  
  
  Komplexität:




Zeitkomplexität: O(n²) (aufgrund der verschachtelten Schleifen für jeden Preis).

Raumkomplexität: O(n) (für das Ergebnisarray).



  
  
  Beispielausgaben:



Für Preise = [8, 4, 6, 2, 3] ist die Ausgabe [4, 2, 4, 2, 3].
Für Preise = [1, 2, 3, 4, 5] ist die Ausgabe [1, 2, 3, 4, 5].
Für Preise = [10, 1, 1, 6] ist die Ausgabe [9, 0, 1, 6].


Dieser Ansatz funktioniert innerhalb der Einschränkungen des Problems (1 <= Preise.Länge <= 500), auch wenn es nicht die optimalste Lösung ist.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt vonEndgültige Preise mit Sonderrabatt in einem Geschäft. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!