𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗧𝗮𝗴 𝟱: 𝗗𝗲𝗿 𝗯𝗲𝘀𝘁𝗲 𝗭𝗲𝗶𝘁𝗽𝘂𝗻𝗸𝘁 𝘇𝘂𝗺 𝗞𝗮𝘂𝗳𝗲𝗻 𝘂𝗻𝗱 𝗩𝗲𝗿𝗸𝗮𝘂𝗳𝗲𝗻 𝘃𝗼𝗻 𝗔𝗸𝘁𝗶𝗲𝗻

Leetcode 121 fordert Sie auf, den besten Zeitpunkt zum Kaufen und Verkaufen einer Aktie zu finden. Sie erhalten ein Array von Preisen. Jeder Index entspricht einem Tag. Der Wert ist der Preis an diesem Tag.

Das Ziel ist einfach: Kaufen Sie an einem Tag und verkaufen Sie an einem zukünftigen Tag, um den maximalen Gewinn zu erzielen. Wenn kein Gewinn möglich ist, geben Sie 0 zurück.

Die Problembeschränkungen:

  • Array-Länge bis zu 100.000.
  • Preise bis zu 10.000.
  • Sie müssen verkaufen, nachdem Sie gekauft haben.

Ansatz 1: Die naive Methode (Brute Force)

Der Brute-Force-Ansatz prüft jedes einzelne Kauf- und Verkaufspaar. Dies erfordert zwei Schleifen.

  • Zeitkomplexität: O(n²)
  • Problem: Es ist zu langsam.

Wenn Sie 1.000 Tage haben, führen Sie 1.000.000 Prüfungen durch. Wenn Sie 100.000 Tage haben, führen Sie 10.000.000.000 Prüfungen durch. Dies führt auf Leetcode zu einem Timeout.

Ansatz 2: Die optimierte Methode (One Pass)

Sie können dies in einem einzigen Durchlauf lösen, indem Sie zwei Variablen verwenden: minPrice und maxProfit.

  • Zeitkomplexität: O(n)
  • Platzkomplexität: O(1)

So funktioniert es:

  1. Setzen Sie minPrice auf Unendlich.
  2. Setzen Sie maxProfit auf 0.
  3. Durchlaufen Sie jeden Preis.
  4. Wenn der aktuelle Preis niedriger als minPrice ist, aktualisieren Sie minPrice.
  5. Wenn der aktuelle Preis minus minPrice größer als maxProfit ist, aktualisieren Sie maxProfit.

Beispielhafter Ablauf mit den Preisen [7, 1, 5, 3, 6, 4]:

  • Tag 1: Preis 7. minPrice wird zu 7. maxProfit bleibt 0.
  • Tag 2: Preis 1. minPrice wird zu 1. maxProfit bleibt 0.
  • Tag 3: Preis 5. 5 - 1 = 4. maxProfit wird zu 4.
  • Tag 4: Preis 3. 3 - 1 = 2. maxProfit bleibt 4.
  • Tag 5: Preis 6. 6 - 1 = 5. maxProfit wird zu 5.
  • Tag 6: Preis 4. 4 - 1 = 3. maxProfit bleibt 5.

Endergebnis: 5.

Die optimierte Version gewinnt, weil sie jeden Preis nur einmal betrachtet. Sie skaliert gut für große Datensätze.

Quelle: https://dev.to/afuji/leetcode-150-day-5-best-time-to-buy-and-sell-stock-naive-vs-optimized-4mk1