Best Time to Buy and Sell Stock

+10

Du erhältst eine Liste prices, wobei prices[i] der Preis einer Aktie am Tag i ist. Du kannst an einem Tag eine Aktie kaufen und sie an einem späteren Tag verkaufen. Gib den größtmöglichen Gewinn zurück, den du erzielen kannst, oder 0, wenn jeder mögliche Handel zu einem Verlust führt.

Funktion

maxProfit(prices: integer-array) → integer

pricesinteger-array: der Aktienkurs an jedem Tag, der Reihe nach
Gibt zurückinteger: der größte Gewinn aus einem Kauf und einem späteren Verkauf oder 0

Einschränkungen

1 ≤ prices.length ≤ 10⁵
0 ≤ prices[i] ≤ 10⁴
Du tätigst höchstens einen Handel und verkaufst an einem späteren Tag, als du kaufst.

Beispiele

Eingabe: prices = [7, 2, 5, 9, 1, 4]
Ausgabe: 7
Erklärung: Kaufe an Tag 1 für 2 und verkaufe an Tag 3 für 9, um einen Gewinn von 7 zu erzielen. Der günstigste Preis, 1 an Tag 4, kommt nach den 9, daher bringt der beste Verkauf danach nur 3 ein.

Weiterführende Frage

Was wäre, wenn du beliebig viele Trades machen darfst, aber jeweils höchstens eine Aktie halten darfst?

Lösung

Du musst kaufen, bevor du verkaufst. Daher ist die Antwort nicht der höchste Preis minus dem niedrigsten. Für jeden Tag, an dem du verkaufen könntest, ist der beste Kauf der günstigste Tag davor. Wenn du beim Durchgehen den niedrigsten Preis festhältst, lässt sich das Problem in einem einzigen Durchlauf lösen.

Probiere jedes Kauf- und Verkaufspaar aus

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Jeder Handel besteht aus einem Kauftag und einem späteren Verkaufstag. Probiere also jedes Paar aus und behalte die größte Differenz. Wenn du den besten Gewinn bei 0 startest, ist auch die Entscheidung, nicht zu handeln, abgedeckt. Jeder zulässige Handel wird geprüft, daher ist die Antwort korrekt.

Eine Liste mit n Preisen hat ungefähr n²/2 Paare: 100,000 Tage bedeuten ungefähr 5 Milliarden Subtraktionen.

Algorithmus

Setze best auf 0.
Durchlaufe jeden Kauftag buy.
Durchlaufe für jeden davon jeden Verkaufstag sell, der danach liegt.
Berechne prices[sell] minus prices[buy] und speichere das Ergebnis in best, wenn es größer ist.
Gib best zurück.

def maxProfit(prices):
    best = 0
    n = len(prices)
    for buy in range(n):
        for sell in range(buy + 1, n):
            best = max(best, prices[sell] - prices[buy])
    return best

Ein Durchlauf mit dem bisher niedrigsten Preis

Idee

Lege den Verkaufstag i fest. Der beste Kauftag ist der günstigste Tag bis i, daher bringt der beste Handel, der an Tag i endet, prices[i] abzüglich des bisher niedrigsten Preises ein. Jedem Verkaufstag wird sein bester Kauftag zugeordnet, also ist der größte dieser Gewinne die Antwort. An einem Tag, an dem ein neues Tief erreicht wird, beträgt der Gewinn 0, genauso wie bei keinem Handel.

Der Durchlauf liest jeden Preis einmal und behält zwei Zahlen im Blick, lowest und best: O(n) Zeit und O(1) Speicherplatz.

Algorithmus

Setze lowest auf den ersten Preis und best auf 0.
Gehe die Preise der Reihe nach durch.
Wenn der aktuelle Preis unter lowest liegt, setze ihn als neues lowest.
Berechne den aktuellen Preis minus lowest und speichere das Ergebnis in best, wenn es größer ist.
Gib best zurück.

def maxProfit(prices):
    lowest = prices[0]
    best = 0
    for price in prices:
        if price < lowest:
            lowest = price
        elif price - lowest > best:
            best = price - lowest
    return best

Stolperfallen und Grenzfälle

Den höchsten Preis abzüglich des niedrigsten Preises zurückgeben. Bei [7, 2, 5, 9, 1, 4] ergibt das 8, aber die 1 kommt nach der 9. Die Antwort ist 7.
Zulassen, dass die Antwort negativ wird. Bei [9, 7, 4, 3, 1] ist die beste Differenz -1; setze best auf 0 und nicht auf die erste Differenz.
lowest auf 0 setzen. Jeder Gewinn entspricht dann dem Preis selbst, daher gibt [9, 7, 4, 3, 1] 9 zurück. Setze es auf den ersten Preis.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von „Best Time to Buy and Sell Stock“?

Die Lösung mit einem Durchlauf benötigt für n Tage O(n) Zeit, da sie jeden Preis einmal liest, und O(1) zusätzlichen Speicherplatz: den bisher niedrigsten Preis und den besten Gewinn. Jede mögliche Kombination von zwei Tagen auszuprobieren, benötigt O(n²) Zeit.

Warum nicht den niedrigsten Preis vom höchsten Preis abziehen?

Der niedrigste Preis kann nach dem höchsten kommen, und du musst kaufen, bevor du verkaufst. In [7, 2, 5, 9, 1, 4] kommt die 1 nach der 9, also kauft der beste zulässige Handel bei 2 und verkauft bei 9 für einen Gewinn von 7.

Ist „Best Time to Buy and Sell Stock“ ein Problem der dynamischen Programmierung?

Du kannst es auf beide Arten betrachten. Der bisher niedrigste Preis ist ein kleiner Zustand, den du täglich aktualisierst – das ist die dynamische Programmierung. Jeden Verkauf mit dem günstigsten früheren Tag zu kombinieren, ist der Greedy-Ansatz. Beide führen zum selben Code mit einem einzigen Durchlauf.

def maxProfit(prices):
    # Schreibe hier den Code

Test #1

Test #2

Argument

prices = [7, 2, 5, 9, 1, 4]

Erwartete Ausgabe