Best Time to Buy and Sell Stock
Otrzymujesz listę prices, w której prices[i] oznacza cenę jednej akcji w dniu i. Możesz kupić jedną akcję jednego dnia i sprzedać ją w późniejszym dniu. Zwróć największy możliwy zysk albo 0, jeśli każda możliwa transakcja przynosi stratę.
Funkcja
- pricesinteger-array
- cena akcji każdego dnia, w kolejności
- Zwracainteger
- największy zysk z jednego zakupu i późniejszej sprzedaży albo 0
Ograniczenia
1 ≤ prices.length ≤ 1050 ≤ prices[i] ≤ 104- Wykonujesz najwyżej jedną transakcję i sprzedajesz w późniejszym dniu niż kupujesz.
Przykłady
- Wejście
- prices = [7, 2, 5, 9, 1, 4]
- Wyjście
- 7
- Wyjaśnienie
- Kup w dniu 1 za 2 i sprzedaj w dniu 3 za 9, aby osiągnąć zysk w wysokości 7. Najniższa cena, 1 w dniu 4, pojawia się po 9, więc najlepsza sprzedaż po niej przynosi tylko 3.
- Wejście
- prices = [9, 7, 4, 3, 1]
- Wyjście
- 0
- Wyjaśnienie
- Cena spada każdego dnia, więc każda sprzedaż byłaby poniżej ceny zakupu. Nie dokonujesz transakcji, a zysk wynosi 0.
Pytanie dodatkowe
Co jeśli możesz wykonać dowolną liczbę transakcji, mając jednocześnie najwyżej jedną akcję?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Sprzedaż zawsze następuje po zakupie. Wybierz dzień sprzedaży: który dzień zakupu przyniesie największy zysk?
Dla danego dnia sprzedaży najlepszym dniem zakupu jest najtańszy dzień przed nim. Nie musisz za każdym razem szukać tego dnia ponownie, jeśli pamiętasz o nim, idąc naprzód.
Przechodź przez dni po kolei i zapamiętuj dwie liczby: najniższą dotychczasową cenę oraz najlepszy dotychczasowy zysk. Każdego dnia porównuj dzisiejszą cenę pomniejszoną o najniższą cenę z najlepszym zyskiem, a następnie aktualizuj najniższą cenę.
Rozwiązanie
Musisz kupić przed sprzedażą, więc odpowiedzią nie jest najwyższa cena minus najniższa. Dla każdego dnia, w którym możesz sprzedać, najlepszym dniem na zakup jest najtańszy dzień przed nim. Śledzenie tej najniższej ceny podczas przechodzenia przez kolejne dni pozwala rozwiązać problem w jednym przebiegu.
Wypróbuj każdą parę kupna i sprzedaży
Poprawne, ale nie kończy się na największych testach
Intuicja
Każda transakcja składa się z dnia zakupu i późniejszego dnia sprzedaży, więc sprawdź każdą parę i zachowaj największą różnicę. Ustawienie najlepszego zysku początkowo na 0 uwzględnia możliwość nieprzeprowadzania transakcji. Sprawdzana jest każda dozwolona transakcja, więc wynik jest poprawny.
Lista n cen zawiera około n²/2 par: 100 000 dni oznacza około 5 miliardów odejmowań.
Algorytm
- Ustaw
bestna 0. - Przejdź przez każdy dzień zakupu
buy. - Dla każdego z nich przejdź przez każdy późniejszy dzień sprzedaży
sell. - Oblicz różnicę
prices[sell]iprices[buy], a jeśli jest większa, zapisz ją wbest. - Zwróć
best.
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
Jedno przejście z najniższą dotychczasową ceną
Intuicja
Ustal dzień sprzedaży i. Najlepszym dniem zakupu jest najtańszy dzień do i włącznie, więc najlepsza transakcja kończąca się w dniu i przynosi zysk równy prices[i] minus najniższa dotychczasowa cena. Każdy dzień sprzedaży jest parowany z najlepszym dniem zakupu, więc odpowiedzią jest największy z tych zysków. W dniu, w którym pojawia się nowa najniższa cena, zysk wynosi 0 — tyle samo, co przy braku transakcji.
Przejście odczytuje każdą cenę raz i przechowuje dwie liczby: lowest i best: czas O(n) i pamięć O(1).
Algorytm
- Ustaw
lowestna pierwszą cenę, abestna 0. - Przejdź po cenach w podanej kolejności.
- Jeśli bieżąca cena jest niższa niż
lowest, ustaw ją jako nową wartośćlowest. - Oblicz różnicę między bieżącą ceną a
lowesti zapisz ją wbest, jeśli jest większa. - Zwróć
best.
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
Pułapki i przypadki brzegowe
- Odjęcie najniższej ceny od najwyższej. Dla
[7, 2, 5, 9, 1, 4]daje to 8, ale 1 pojawia się po 9. Odpowiedź to 7. - Pozwolenie, by odpowiedź była ujemna. W przypadku
[9, 7, 4, 3, 1]najlepsza różnica wynosi -1; ustaw początkową wartośćbestna 0, a nie na pierwszą różnicę. - Ustawienie początkowej wartości
lowestna 0. Każdy zysk będzie wtedy równy samej cenie, więc[9, 7, 4, 3, 1]zwróci 9. Ustaw ją na pierwszą cenę.
Najczęstsze pytania3
Jaka jest złożoność czasowa problemu „Best Time to Buy and Sell Stock”?
Rozwiązanie w jednym przejściu działa w czasie O(n) dla n dni, ponieważ odczytuje każdą cenę raz, i wymaga O(1) dodatkowej przestrzeni: najniższej dotąd ceny i najlepszego zysku. Sprawdzenie każdej pary dni zajmuje O(n²) czasu.
Dlaczego nie odjąć najniższej ceny od najwyższej?
Najniższa cena może wystąpić po najwyższej, a musisz kupić przed sprzedażą. W [7, 2, 5, 9, 1, 4] liczba 1 występuje po liczbie 9, więc najlepsza dozwolona transakcja polega na kupnie za 2 i sprzedaży za 9, co daje zysk 7.
Czy „Best Time to Buy and Sell Stock” to problem programowania dynamicznego?
Możesz odczytać to na oba sposoby. Dotychczasowa najniższa cena to niewielki element stanu, który aktualizujesz każdego dnia — tak wygląda podejście programowania dynamicznego. Łączenie każdej sprzedaży z najtańszym wcześniejszym dniem to podejście zachłanne. Oba prowadzą do tego samego kodu działającego w jednym przebiegu.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def maxProfit(prices):
# Napisz kod tutajTest #1
Test #2
Argument
prices = [7, 2, 5, 9, 1, 4]
Oczekiwany wynik
7