Stos monotoniczny: następny większy element
Odpowiadanie na zapytania o zakres w jednym przebiegu
Stos monotoniczny: następny większy element to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Problem następnego większego elementu
Dla każdej liczby należy znaleźć pierwszą większą wartość po jej prawej stronie. Brute force wymaga O(n²), ale stos monotoniczny rozwiązuje ten problem w jednym przejściu.
Co oznacza monotoniczność
Stos monotoniczny przechowuje wartości w uporządkowanej kolejności, tutaj malejącej, więc w chwili naruszenia tego porządku wiadomo, że znaleziono odpowiedź.
Przechowuj indeksy, nie wartości
Odkładaj na stos indeksy, a nie same liczby. Dzięki temu dokładnie wiadomo, którą pozycję uzupełnić, gdy pojawi się większy element.
stack = []
ans = [-1] * len(nums)Przejdź od lewej do prawej
Przejdź po tablicy jeden raz. Przy każdym indeksie zdejmiesz rozwiązane elementy ze stosu albo odłożysz bieżący indeks do późniejszego rozpatrzenia.
for i in range(len(nums)):Zdejmuj mniejsze elementy
Dopóki bieżąca wartość jest większa od wartości na indeksie znajdującym się na szczycie, ten element na szczycie właśnie znalazł swój następny większy element.
while stack and nums[i] > nums[stack[-1]]:Zapisz odpowiedź
Zdejmij indeks ze szczytu i ustaw jego odpowiedź na bieżącą wartość. Każdy indeks zostaje rozstrzygnięty dokładnie raz, dzięki czemu praca ma charakter liniowy.
j = stack.pop()
ans[j] = nums[i]Dodaj i kontynuuj
Po rozstrzygnięciu wszystkich mniejszych elementów odłóż bieżący indeks, aby mógł poczekać na swój przyszły większy element.
stack.append(i)Pozostałe elementy nie mają odpowiedzi
Indeksy pozostające na stosie na końcu nigdy nie napotkały większej wartości. Zachowują domyślną wartość -1, która oznacza, że taki element nie istnieje.
Dlaczego to O(n)
Każdy indeks zostaje dodany raz i zdjęty raz. Nawet z wewnętrzną pętlą while całkowity nakład pracy dla całego przejścia pozostaje liniowy.
Odwróć schemat dla następniejszego mniejszego elementu
Potrzebny jest następny mniejszy element? Utrzymuj stos rosnący, odwracając porównanie z większe niż na mniejsze niż.
while stack and nums[i] < nums[stack[-1]]:Schemat, nie sztuczka
Zapytania o rozpiętość, ceny akcji i pola histogramów korzystają z tej samej idei. Stos monotoniczny to podstawowy schemat konkursowy, który warto zapamiętać.
Szybkie sprawdzenie
Rozwiązują Państwo problem następnego większego elementu za pomocą stosu monotonicznego. Dlaczego całkowity czas działania jest liniowy?
Podsumowanie: jedno przejście, wiele odpowiedzi
Użyli Państwo malejącego stosu monotonicznego indeksów, aby znaleźć następne większe elementy w czasie O(n). Ten schemat otwiera drogę do rozwiązania wielu problemów dotyczących rozpiętości. 🚀
Ucz się Coding Interview Prep dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 90
- Lekcje
- 360
Często zadawane pytania
Czy lekcja „Stos monotoniczny: następny większy element” jest bezpłatna?
Tak — pełny tekst „Stos monotoniczny: następny większy element” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Stos monotoniczny: następny większy element”?
Odpowiadanie na zapytania o zakres w jednym przebiegu Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Stos monotoniczny: następny większy element”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Stosy do dopasowywania nawiasów
- Stos monotoniczny: następny większy element
- Kolejki i collections.deque
- Maksimum w przesuwanym oknie za pomocą deque