Stock Span Problem
Otrzymujesz cenę zamknięcia akcji każdego dnia: prices[i] to cena w dniu i. Rozpiętość dla dnia i to liczba kolejnych dni, kończących się w dniu i i obejmujących go, w których cena była mniejsza lub równa prices[i].
Zwróć rozpiętość dla każdego dnia, w tej samej kolejności co w prices. Każda rozpiętość wynosi co najmniej 1, ponieważ dany dzień zawsze liczy się sam.
Funkcja
- pricesinteger-array
- cena każdego dnia, w kolejności
- Zwracainteger-array
- zakres każdego dnia, w tej samej kolejności
Ograniczenia
1 ≤ prices.length ≤ 1041 ≤ prices[i] ≤ 105- Wcześniejszy dzień z tą samą ceną wlicza się do okresu; zatrzymuje go dopiero cena ściśle wyższa.
Przykłady
- Wejście
- prices = [31, 27, 14, 21, 30, 18, 40]
- Wyjście
- [1, 1, 1, 2, 4, 1, 7]
- Wyjaśnienie
- Dzień 3. przy wartości 21 cofa się o 14 i zatrzymuje na 27: rozpiętość 2. Dzień 4. przy wartości 30 zatrzymuje się na 31: rozpiętość 4. Dzień 6. przy wartości 40 przewyższa wszystkie wcześniejsze ceny i obejmuje wszystkie 7 dni.
- Wejście
- prices = [8, 8, 3, 8]
- Wyjście
- [1, 2, 1, 4]
- Wyjaśnienie
- Równe ceny się liczą, więc dzień 1 z ceną 8 obejmuje dzień 0 i otrzymuje wynik 2. Dzień 3 z ceną 8 obejmuje dzień 3 i obie wcześniejsze ceny 8, czyli zakres wynosi 4.
- Wejście
- prices = [50, 40, 30, 20]
- Wyjście
- [1, 1, 1, 1]
- Wyjaśnienie
- Każdy dzień jest tańszy niż poprzedni, więc żaden zakres nie sięga dalej niż sam dzień, a każdy zakres ma długość 1.
Pytanie dodatkowe
Ceny napływają teraz pojedynczo i musisz podawać każdy zakres, gdy tylko pojawi się jego cena. Które podejście nadal działa i co zachowuje między wywołaniami?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Odliczanie wstecz każdego dnia powtarza pracę: przy 8000 dniach w tej samej cenie sam ostatni dzień wymaga cofnięcia się o 8000 dni. Cofając się od dzisiaj, które wcześniejsze dni możesz na dobre pominąć?
Gdy dzisiejsza cena jest co najmniej tak wysoka jak cena z któregoś wcześniejszego dnia, ten wcześniejszy dzień nigdy nie może być tym, który zatrzyma późniejszy zakres: dzisiejszy dzień jest bliżej i jego cena jest co najmniej tak wysoka. Znaczenie mają tylko te dni, których ceny są wyższe niż ceny wszystkich późniejszych dni, a ich ceny maleją od najstarszej do najnowszej.
Przechodź przez dni w kolejności i zachowuj na stosie, jako indeksy, wcześniejsze dni, które nadal mają znaczenie. Zanim podasz odpowiedź dla dzisiejszego dnia, zdejmij ze stosu każdy dzień, którego cena jest nie większa niż dzisiejsza. Pusty stos oznacza, że zakres sięga dnia 0; w przeciwnym razie zaczyna się dzień po dniu pozostawionym na wierzchu. Następnie dodaj dzisiejszy dzień na stos.
Rozwiązanie
Rozpiętość dnia kończy się na najbliższym wcześniejszym dniu z ceną ściśle wyższą. Cofanie się w poszukiwaniu takiego dnia kosztuje do n kroków na każdy dzień. Zamiast tego zachowuj tylko te dni, które mogą jeszcze wyznaczyć koniec przyszłej rozpiętości: stos indeksów o ściśle malejących cenach pozwala znaleźć każdą granicę w jednym przebiegu.
Odliczaj wstecz od każdego dnia
Poprawne, ale nie kończy się na największych testach
Intuicja
Postępuj zgodnie z definicją. Dla dnia i cofaj się o jeden dzień, dopóki cena tego dnia jest nie większa niż prices[i], wliczając dzień i. Pierwsza ściśle wyższa cena lub początek tablicy kończy przebieg.
Żaden przebieg nie wykorzystuje ponownie wcześniejszego. Przy cenach stałych lub rosnących każdy przebieg cofa się aż do dnia 0: n = 10^4 dni oznacza około 5 × 10^7 kroków.
Algorytm
- Utwórz
span, tablicę o długości takiej jakprices. - Dla każdego dnia
iustaw licznik na 0, a wskaźnikjnai. - Gdy
j ≥ 0iprices[j] ≤ prices[i], zwiększ licznik o 1 i przesuńjo jeden dzień wstecz. - Zapisz licznik w
span[i]. Po ostatnim dniu zwróćspan.
def stockSpan(prices):
span = []
for i in range(len(prices)):
count = 0
j = i
# Count today and every earlier day in a row that is not more expensive.
while j >= 0 and prices[j] <= prices[i]:
count += 1
j -= 1
span.append(count)
return spanMonotoniczny stos dni o wyższych wartościach
Intuicja
Nazwij najbliższy wcześniejszy dzień z ściśle wyższą ceną blokującym. Rozpiętość to today - blocker albo today + 1, jeśli takiego dnia nie ma.
W pierwszym przykładzie cena w dniu 3 wynosi 21, a w dniu 4 — 30. Każdy późniejszy przebieg najpierw dociera do dnia 4, a każda cena, która przekracza 30, przekracza też 21, więc dzień 3 już nigdy nie może blokować. Ogólnie, gdy nadchodzi dzisiejszy dzień, każdy wcześniejszy kandydat, którego cena jest nie wyższa niż dzisiejsza, przestaje być brany pod uwagę: zdejmij go ze stosu. Dzień pozostający na szczycie stosu jest dzisiejszym dniem blokującym. Następnie dodaj dzisiejszy dzień na stos.
Ceny na stosie ściśle maleją od dołu do góry, więc pierwsza z nich, która pozostaje na stosie, jest najbliższą wyższą ceną. W pierwszym przykładzie dzień 4 zdejmuje ze stosu dni 3 i 1, a zatrzymuje się na dniu 0, co daje rozpiętość 4 - 0 = 4. Każdy dzień jest dodawany na stos raz i zdejmowany z niego co najwyżej raz, więc przebieg działa w czasie O(n).
Algorytm
- Utwórz tablicę
spani pusty stos indeksów dni. - Dla każdego dnia
todayzdejmuj indeksy ze stosu, dopóki ich cena jest mniejsza lub równaprices[today]. - Jeśli stos jest pusty, span wynosi
today + 1; w przeciwnym razie jest totodayminus indeks na wierzchu stosu. - Umieść
todayna stosie i przejdź do następnego dnia. Zwróćspan.
def stockSpan(prices):
span = [0] * len(prices)
higher = [] # indices of earlier days, prices strictly falling toward the top
for today, price in enumerate(prices):
# A day that is not more expensive than today can never stop a later span.
while higher and prices[higher[-1]] <= price:
higher.pop()
# The span reaches back to the nearest more expensive day, or to day 0.
span[today] = today - higher[-1] if higher else today + 1
higher.append(today)
return span
Pułapki i przypadki brzegowe
- Usuwanie elementu przy
<zamiast<=. W[8, 8, 3, 8]ostatni dzień ma rozpiętość 4; zatrzymanie się na wcześniejszej 8 daje 2. - Wpisanie
todayzamiasttoday + 1, gdy stos jest pusty. Dzień 0 musi otrzymać 1, a nie 0. - Usuwanie tylko jednego elementu dziennie. W pierwszym przykładzie 40 musi usunąć dni 5, 4 i 0. Zatrzymaj się po dniu 5, a dzień 4 wygląda jak przeszkoda — rozpiętość wynosi wtedy 2 zamiast 7.
- W Lua i R tablice zaczynają się od 1. Przy indeksowaniu od 1 rozpiętość dla pustego stosu wynosi
today, a nietoday + 1.
Najczęstsze pytania4
Jaka jest złożoność czasowa problemu rozpiętości cen akcji?
Czas O(n) i dodatkowa przestrzeń O(n) dzięki stosowi monotonicznemu, ponieważ każdy dzień opuszcza stos co najwyżej raz. Cofanie się od każdego dnia ma złożoność O(n²), gdy ceny stale rosną lub pozostają bez zmian.
Czy stos powinien przechowywać ceny czy indeksy dni?
Indeksy dni. Rozpiętość to liczba dni, a tylko indeks blokady pozwala ją określić. prices[index] odczytuje cenę do porównania.
Czy problem zakresu cen akcji można rozwiązać bez użycia osobnego stosu?
Tak. Zacznij od j = today - 1; dopóki j ≥ 0 i prices[j] ≤ prices[today], przeskakuj do j - span[j], ponieważ cena z każdego dnia w tym przedziale jest co najwyżej równa prices[j]. Przedział ma długość today - j. Skoki trafiają tylko na dni, które znalazłyby się na stosie, więc przejście pozostaje w czasie O(n).
Czy problem spanów cen akcji jest problemem poprzedniego większego elementu?
Tak, mierzone w dniach: dla każdego dnia znajdź najbliższy wcześniejszy dzień z ściśle wyższą ceną i podaj, jak daleko wstecz on wypada. Zmień kierunek przeszukiwania lub porównanie, a ten sam stos pozwoli znaleźć następny większy, następny mniejszy lub poprzedni mniejszy element.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def stockSpan(prices):
# Wpisz kod tutajTest #1
Test #2
Test #3
Argument
prices = [31, 27, 14, 21, 30, 18, 40]
Oczekiwany wynik
[1, 1, 1, 2, 4, 1, 7]