Next Greater Element I
Otrzymujesz dwie tablice różnych liczb całkowitych, nums1 i nums2, a każda wartość z nums1 występuje również w nums2. Następny większy element wartości x to pierwsza wartość po prawej stronie x w nums2, która jest większa od x, lub -1, jeśli taka wartość nie istnieje.
Zwróć tablicę zawierającą następny większy element każdej wartości z nums1, w kolejności zgodnej z nums1.
Funkcja
- nums1integer-array
- wartości do odpowiedzi, wszystkie znajdują się w nums2
- nums2integer-array
- tablica, w której patrzysz na prawo od każdej wartości
- Zwracainteger-array
- następny większy element każdej wartości nums1 lub -1, w kolejności nums1
Ograniczenia
1 ≤ nums1.length ≤ nums2.length ≤ 1040 ≤ nums1[i], nums2[i] ≤ 104- Wszystkie wartości w
nums1są różne, a wszystkie wartości wnums2są różne. - Każda wartość z
nums1występuje wnums2.
Przykłady
- Wejście
- nums1 = [3, 8, 1]nums2 = [1, 6, 3, 8, 2]
- Wyjście
- [8, -1, 6]
- Wyjaśnienie
- Po 3 w
nums2występują 8 i 2, a 8 jest pierwszą wartością większą od 3. Po 8 występuje tylko 2, więc 8 otrzymuje -1. Wartość zaraz po 1 to 6, która jest już większa.
- Wejście
- nums1 = [5, 2]nums2 = [2, 9, 5, 4]
- Wyjście
- [-1, 9]
- Wyjaśnienie
- Tylko 4 występuje po 5, a 4 jest mniejsze, więc 5 otrzymuje -1. Wartość bezpośrednio po 2 to 9. Odpowiedzi są podane w kolejności
nums1, a nie w kolejnościnums2.
- Wejście
- nums1 = [10, 0]nums2 = [0, 10, 11]
- Wyjście
- [11, 10]
- Wyjaśnienie
- Pierwsza wartość po 10 to 11. Pierwsza wartość po 0 to 10, która jest większa, więc 0 otrzymuje 10, mimo że 11 pojawia się później i jest jeszcze większa.
+14 ukrytych testów przy wysłaniu
Pytanie dodatkowe
Dla każdej pozycji w nums2 czy potrafisz zwrócić, o ile kroków w prawo znajduje się następny większy element, wykonując to samo pojedyncze przejście?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Skanowanie w prawo od każdej wartości
nums1może kosztować do 10^4 kroków dla każdej wartości. Odpowiedzi zależą wyłącznie odnums2. Czy potrafisz wyznaczyć następny większy element dla każdej wartościnums2w jednym przebiegu, a następnie wyszukać wartości znums1?Przechodź przez
nums2od lewej do prawej i zachowuj wartości, które nie napotkały jeszcze większej wartości. Gdy pojawi się nowa wartość, jest ona odpowiedzią dla każdej oczekującej wartości mniejszej od niej. Oczekujące wartości zawsze tworzą ciąg malejący, więc mniejsze z nich znajdują się na szczycie stosu.Dla każdej wartości
nums2: dopóki wartość na szczycie stosu jest od niej mniejsza, zdejmuj ją ze stosu i zapisuj bieżącą wartość jako jej odpowiedź w mapie haszującej. Następnie umieść bieżącą wartość na stosie. Na końcu znajdź w mapie odpowiedź dla każdej wartościnums1, a dla wartości, która nigdy nie została zdjęta ze stosu, zwróć -1.
Rozwiązanie
Dla jednej wartości odpowiedzią jest skanowanie w prawo, ale skanowanie dla każdej wartości z nums1 wymaga nawet nums1.length × nums2.length kroków. Odpowiedzi zależą wyłącznie od nums2, więc możesz jednocześnie znaleźć następny większy element dla każdej wartości z nums2 za pomocą stosu monotonicznego, przechować je w mapie haszującej, a następnie znaleźć odpowiedzi dla nums1 przez wyszukiwanie.
Znajdź każdą wartość i przesuwaj się w prawo
Poprawne, ale nie kończy się na największych testach
Intuicja
Postępuj zgodnie z definicją. Dla wartości x z nums1 przechodź przez nums2, aż dotrzesz do x. Następnie idź dalej i zatrzymaj się przy pierwszej wartości większej niż x. Jeśli dojdziesz do końca i jej nie znajdziesz, odpowiedzią jest -1.
To poprawne, ponieważ podczas skanowania odwiedzasz po kolei wartości znajdujące się na prawo od x, więc pierwsza napotkana większa wartość jest pierwszą większą wartością, jaka tam występuje.
Jest to powolne, gdy odpowiedzi są daleko lub ich brakuje. Jeśli nums2 jest malejące, żadne skanowanie nie znajdzie większej wartości, a każde przejście dla wartości z nums1 będzie trwało aż do końca. Przy m wartościach w nums1 i n w nums2 daje to maksymalnie m × n kroków: 10^8, gdy obie tablice zawierają 10^4 wartości. Każde skanowanie obejmuje też fragmenty, które zostały już wcześniej przeskanowane.
Algorytm
- Przejdź pętlą po każdej wartości
xznums1. - Znajdź indeks
j, dla któregonums2[j]jest równex. - Przeszukaj
nums2odj+1i zatrzymaj się na pierwszej wartości większej niżx. - Dodaj tę wartość albo -1, jeśli przeszukiwanie dotarło do końca.
- Zwróć zebrane odpowiedzi.
def nextGreaterElement(nums1, nums2):
result = []
for x in nums1:
j = 0
while nums2[j] != x:
j += 1
answer = -1
for k in range(j + 1, len(nums2)):
if nums2[k] > x:
answer = nums2[k]
break
result.append(answer)
return resultStos monotoniczny i mapa haszująca
Intuicja
Odwróć sposób myślenia o zadaniu. Zamiast pytać dla każdej wartości, co występuje po niej, przejdź raz przez nums2 i pozwól, by każda nowa wartość odpowiadała wcześniejszym wartościom, które przewyższa. Wartości, które nie mają jeszcze odpowiedzi, przechowuj na stosie. Gdy pojawi się nowa wartość, zdejmuj ze szczytu wszystkie mniejsze wartości: nowa wartość jest pierwszą większą wartością po ich prawej stronie, więc stanowi ich odpowiedź. Następnie umieść na stosie nową wartość, która wciąż czeka na swoją odpowiedź.
Prześledźmy nums2 = [1, 6, 3, 8, 2]. Umieść na stosie 1. Następnie pojawia się 6 i przewyższa 1, więc 1 mapuje się na 6; umieść 6 na stosie. Potem pojawia się 3, nie przewyższa 6 i zostaje umieszczone na szczycie: stos ma postać [6, 3]. Następnie 8 zdejmuje 3 i 6, więc obie wartości mapują się na 8; umieść 8 na stosie. Potem zostaje umieszczone 2. Stos kończy działanie w postaci [8, 2], a te dwie wartości nie mają odpowiedzi. Dla nums1 = [3, 8, 1] mapa zwraca [8, -1, 6].
Wartości na stosie są zawsze ułożone malejąco od dołu do góry, ponieważ dana wartość trafia na stos dopiero po zdjęciu wszystkich mniejszych wartości znajdujących się nad nią. Dlatego wystarczy sprawdzać tylko szczyt stosu. Wartość opuszcza stos w chwili pojawienia się pierwszej większej wartości, więc zapisana odpowiedź jest pierwszą taką wartością, a nie największą.
Każda wartość z nums2 trafia na stos raz i jest z niego zdejmowana najwyżej raz, więc wewnętrzna pętla wykonuje łącznie najwyżej n operacji zdejmowania podczas całego przejścia. Wraz z m wyszukiwaniami czas działania wynosi O(n + m). Mapa łączy obie tablice: wartości są różne, więc wartość jest bezpiecznym kluczem, nawet jeśli występuje na różnych pozycjach w nums1 i nums2. Rozwiązania w C i R używają jako mapy tablicy z 10^4+1 miejscami, indeksowanej według wartości, co działa, ponieważ żadna wartość nie przekracza 10^4.
Algorytm
- Utwórz pustą mapę i pusty stos.
- Dla każdej wartości z
nums2zdejmuj ze szczytu stosu każdą mniejszą wartość i przypisz ją w mapie do bieżącej wartości. - Umieść bieżącą wartość na stosie.
- Dla każdej wartości z
nums1zwróć przypisaną jej odpowiedź lub -1, jeśli jej nie ma.
def nextGreaterElement(nums1, nums2):
next_greater = {}
stack = [] # values still waiting for a greater one, decreasing from bottom to top
for value in nums2:
# value is the first greater value to the right of every smaller value on the stack.
while stack and stack[-1] < value:
next_greater[stack.pop()] = value
stack.append(value)
# Whatever is still on the stack has no greater value to its right.
return [next_greater.get(x, -1) for x in nums1]
Pułapki i przypadki brzegowe
Sam stos jest krótki; błędy dotyczą tego, co zapisujesz i gdzie szukasz.
- Zapisywanie największej wartości po prawej zamiast pierwszej większej. W
nums2 = [3, 5, 1, 2, 4, 9, 0]odpowiedzią dla 1 jest 2, a nie 9. - Zwracanie odpowiedzi w kolejności wartości z
nums2albo dla każdej wartości znums2. Wynik zawiera jeden element dla każdej wartości znums1, w jej kolejności. - Zwracanie indeksu zamiast wartości. Zadanie wymaga podania samej większej wartości.
- Odczytywanie
nums2pod indeksem, który dana wartość ma wnums1. Ta sama wartość znajduje się na różnych pozycjach w obu tablicach; znajdź ją po wartości — do tego służy mapa. - Zapominanie o wartościach pozostawionych na stosie na końcu. Nie napotkały one większej wartości, więc ich odpowiedzią jest -1; wyszukanie w mapie bez wartości domyślnej kończy się błędem albo nie zwraca niczego dla tych wartości.
- Szukanie w lewo albo zawijanie się na początek
nums2. Liczą się tylko wartości po prawej, a tablica nie zawija się.
Najczęstsze pytania4
Jaka jest złożoność czasowa problemu Next Greater Element I?
Rozwiązanie ze stosem monotonicznym działa w czasie O(n + m), gdzie n to długość nums2, a m to długość nums1. Każda wartość z nums2 jest dodawana i usuwana ze stosu co najwyżej raz, a dla każdej wartości z nums1 wykonywane jest jedno wyszukanie w mapie. Mapa i stos zajmują O(n) pamięci. Przeszukiwanie w prawo od każdej wartości zajmuje czas O(n·m).
Czym jest stos monotoniczny?
To stos, którego wartości są uporządkowane od dołu do góry — tutaj malejąco. Zanim dodasz nową wartość na stos, zdejmujesz z niego wszystko, co zaburzyłoby porządek. Właśnie podczas zdejmowania wykonywana jest praca: każda zdjęta wartość znalazła swoją pierwszą większą wartość po prawej stronie. To rozwiązanie pozwala odpowiadać na pytania o następną większą, następną mniejszą i podobne wartości w czasie liniowym.
Dlaczego Next Greater Element I potrzebuje mapy haszującej?
Przejście po stosie generuje odpowiedzi w kolejności, w jakiej wartości opuszczają stos, a kluczem są wartości z nums2. Wynik musi zachowywać kolejność z nums1, w którym te same wartości znajdują się na innych pozycjach. Ponieważ wszystkie wartości są różne, mapa wartości na odpowiedź łączy obie tablice, zapewniając stały czas wyszukiwania dla każdej wartości.
Co się zmieni, jeśli nums2 jest cykliczna?
Wtedy wyszukiwanie większej wartości może być kontynuowane od początku tablicy. Wykonaj ten sam przebieg stosu nad tablicą dwukrotnie, używając indeksu i % n dla i od 0 do 2n-1, i dodawaj wartości do stosu tylko podczas pierwszego przebiegu. Wartości, które po obu przebiegach nadal znajdują się na stosie, nie mają nigdzie większej wartości, więc ich odpowiedzią jest -1.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
Python
def nextGreaterElement(nums1, nums2):
# Wpisz kod tutajPrzypadek 1
Przypadek 2
Przypadek 3
Wejście
nums1 = [3, 8, 1] nums2 = [1, 6, 3, 8, 2]
Oczekiwane
[8, -1, 6]