LeetCode-Problem: Beste Zeit zum Kaufen und Verkaufen von Aktien

Ich habe mich kürzlich mit einem klassischen LeetCode-Problem beschäftigt: „Beste Zeit zum Kaufen und Verkaufen von Aktien.“ Bei diesem Problem müssen Sie den maximalen Gewinn ermitteln, den Sie durch einmaliges Kaufen und Verkaufen einer Aktie erzielen können. Lassen Sie uns auf die verschiedenen Ansätze eingehen, die ich untersucht habe, und auf ihre Komplexität. Hier ist die URL des Problems:

LeetCode 121

Brute-Force-Ansatz (Zeitkomplexität: O(n^2))

Die einfachste Lösung könnte darin bestehen, jedes Element im Array mit allen übrigen Elementen zu vergleichen. Für jeden Preis berechnen wir den Gewinn, den er erzielen würde, wenn er an einem späteren Tag verkauft würde. Anschließend verfolgen wir den maximal erzielten Gewinn. Dieser Ansatz leidet jedoch unter der hohen zeitlichen Komplexität und führte zu einer Zeitlimitüberschreitung.

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

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

Hier ist der Grund: Wir vergleichen jedes Element mit n-1 anderen Elementen, was zu n*(n-1)/2 Vergleichen führt. Dies entspricht ungefähr einer O(n^2)-Zeitkomplexität, die für große Datensätze ineffizient wird. Leider führt dieser Ansatz häufig zu der Fehlermeldung „Zeitlimit überschritten“ bei LeetCode.

Zwei-Zeiger-Ansatz (Zeitkomplexität: O(n))

Um die Effizienz zu verbessern, können wir die Tatsache nutzen, dass wir kaufen, bevor wir verkaufen. Wir können zwei Hinweise vorstellen:

• Kaufen: Zeigt den aktuellen potenziellen Kaufpreis an.
• Verkaufen: Zeigt auf den Verkaufspreiskandidaten.

Die Idee besteht darin, das Preisarray beginnend mit dem dritten Element zu durchlaufen (da die ersten beiden Elemente zum Kaufen und Verkaufen verwendet werden). Wir prüfen kontinuierlich, ob die Differenz zwischen dem Verkaufspreis (aktuelles Element) und dem Kaufpreis größer ist als der aktuelle maximale Gewinn. Wenn dies zutrifft, aktualisieren wir den maximalen Gewinn. Andernfalls aktualisieren wir den Kaufzeiger auf das aktuelle Element (möglicherweise einen niedrigeren Kaufpreis) und verschieben den Verkaufszeiger einen Schritt nach vorne.

Dieser Ansatz bietet eine deutliche Verbesserung der zeitlichen Komplexität und erreicht O(n), da wir das Array nur einmal durchlaufen.

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



<p><img src="/static/imghw/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/172284027594031.png" class="lazy" alt="LeetCode-Problem: Beste Zeit zum Kaufen und Verkaufen von Aktien" loading="lazy"    style="max-width:90%"  style="max-width:90%"></p>

<h2>
  
  
  Gieriger Ansatz (Zeitkomplexität: O(n)) mit Python-Beispiel
</h2>

<p>Mit einem LeetCode-Problem: Beste Zeit zum Kaufen und Verkaufen von Aktien-Ansatz können wir eine ähnliche Zeitkomplexität erreichen. Der Schlüssel hier ist zu verstehen, dass der maximale Gewinn nur dann erzielt werden kann, wenn wir günstig kaufen und teuer verkaufen.  Daher können wir das Preisarray durchlaufen und den bisher ermittelten Mindestpreis verfolgen. Dies stellt den potenziellen Kaufpreis dar.</p>

<p>Hier ist eine Python-Implementierung des LeetCode-Problem: Beste Zeit zum Kaufen und Verkaufen von Aktien-Ansatzes:<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

Hier erfahren Sie immer mehr darüber, wo ich sonst noch in meinem Portfolio zu finden bin

Das obige ist der detaillierte Inhalt vonLeetCode-Problem: Beste Zeit zum Kaufen und Verkaufen von Aktien. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!