Stos monotoniczny: rosnący a malejący
Utrzymywać stos rosnący lub malejący, aby efektywnie odpowiadać na zapytania o następny większy i poprzedni mniejszy element w czasie O(n)
Stos monotoniczny: rosnący a malejący to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 1 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 DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Czym jest stos monotoniczny
Stos monotoniczny to stos, który zachowuje uporządkowanie swoich elementów — od dołu do góry są one zawsze rosnące albo zawsze malejące. Przed dodaniem nowego elementu usuwamy ze stosu wszystkie elementy naruszające niezmiennik monotoniczności. Ta ograniczona struktura umożliwia rozwiązanie w czasie O(n) problemów, które w innym przypadku wymagałyby zagnieżdżonych pętli o złożoności O(n²).
Kluczowa obserwacja jest taka, że każdy element jest dodawany i usuwany co najwyżej raz, więc łączna liczba operacji podczas przechodzenia przez całą tablicę wynosi O(n), a nie O(n²). W chwili usunięcia elementu znaleźliśmy odpowiedź, na którą czekał.
# Monotonic increasing stack (bottom to top: smallest to largest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] > val:
stack.pop() # maintain increasing invariant
stack.append(val)
print('Increasing stack (left-to-right):', stack) # [1, 1, 2, 6]
# Monotonic decreasing stack (bottom to top: largest to smallest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] < val:
stack.pop() # maintain decreasing invariant
stack.append(val)
print('Decreasing stack (left-to-right):', stack) # [9, 6]Next Greater Element I
Problem Next Greater Element polega na znalezieniu dla każdego elementu pierwszego większego elementu po jego prawej stronie. Naiwna podwójna pętla o złożoności O(n²) jest zbyt wolna. Za pomocą malejącego stosu monotonicznego rozwiązujemy ten problem w czasie O(n).
Elementy przetwarzamy od lewej do prawej. Przed dodaniem elementu i usuwamy ze stosu wszystkie elementy mniejsze od nums[i] — nums[i] jest następnym większym elementem dla każdego z nich. Po przetworzeniu wszystkich elementów na stosie pozostają te, które nie mają po swojej prawej stronie większego elementu (wynik = -1).
def next_greater_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # stores indices; stack values are decreasing
for i in range(n):
# Pop elements smaller than nums[i]
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i] # nums[i] is next greater for idx
stack.append(i)
# Remaining elements in stack have no next greater => keep -1
return result
nums = [2, 1, 2, 4, 3]
print(next_greater_element(nums)) # [4, 2, 4, -1, -1]
nums2 = [1, 3, 2, 4]
print(next_greater_element(nums2)) # [3, 4, 4, -1]Następny większy element: śledzenie działania algorytmu
Prześledźmy krok po kroku tablicę [2, 1, 2, 4, 3]. Utrzymujemy malejący stos indeksów, dla których nie znaleziono jeszcze następnego większego elementu.
- i=0, val=2: stos pusty, push 0. Stos: [0]
- i=1, val=1: 1 < nums[0]=2, push 1. Stos: [0,1]
- i=2, val=2: pop 1 (nums[1]=1 < 2), result[1]=2; teraz nums[0]=2 nie jest < 2, push 2. Stos: [0,2]
- i=3, val=4: pop 2 (result[2]=4), pop 0 (result[0]=4), push 3. Stos: [3]
- i=4, val=3: 3 < nums[3]=4, push 4. Stos: [3,4]
- Koniec: elementy stosu [3,4] mają result=-1
def next_greater_trace(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(n):
print(f'i={i} val={nums[i]}: stack={[nums[s] for s in stack]}', end=' => ')
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
print(f'pop {nums[idx]}, NGE={nums[i]};', end=' ')
stack.append(i)
print(f'push {nums[i]}, stack={[nums[s] for s in stack]}')
print('Result:', result)
return result
next_greater_trace([2, 1, 2, 4, 3])Poprzedni mniejszy element
Stosy monotoniczne pozwalają również odpowiadać na zapytania o poprzedni mniejszy element (PSE): dla każdego elementu znajdują najbliższy element po jego lewej stronie, który jest mniejszy. Zamiast wykonywać pop po napotkaniu większego elementu, wykonujemy pop po napotkaniu elementu większego lub równego, a przed wykonaniem push zapisujemy wierzchołek stosu jako PSE.
Zmienia się kierunek działania: nadal przetwarzamy elementy od lewej do prawej, ale zamiast odpowiadać na pytania podczas pop, odpowiadamy na nie tuż przed push. Wierzchołek stosu w tym momencie jest najbliższym mniejszym elementem po lewej stronie. Jeśli stos jest pusty, po lewej stronie nie ma mniejszego elementu (odpowiedź = -1 lub wartość wartownika).
def previous_smaller_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # monotonic increasing (values increase bottom to top)
for i in range(n):
# Pop elements >= current (maintain strictly increasing invariant)
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
# Top of stack is previous smaller element (if exists)
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
nums = [4, 5, 2, 10, 8]
print('PSE:', previous_smaller_element(nums)) # [-1, 4, -1, 2, 2]
nums2 = [1, 3, 2, 5, 4]
print('PSE:', previous_smaller_element(nums2)) # [-1, 1, 1, 2, 2]Codzienne temperatury: oczekiwanie na cieplejsze dni
Problem Codzienne temperatury (LeetCode 739): mając dane dzienne temperatury, należy zwrócić tablicę, w której każda wartość oznacza liczbę dni do wystąpienia wyższej temperatury. Jest to dokładnie schemat następnego większego elementu, ale zamiast większej wartości potrzebujemy liczby dni (różnicy indeksów).
Należy użyć malejącego stosu monotonicznego indeksów. Gdy na indeksie i znajdziemy wyższą temperaturę, zdejmujemy ze stosu wszystkie indeksy j, dla których temps[j] < temps[i], i ustawiamy result[j] = i - j. Pozostałe indeksy nie mają w przyszłości cieplejszego dnia (result = 0).
def daily_temperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices of unresolved days
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
j = stack.pop()
result[j] = i - j # days until warmer
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps)) # [1, 1, 4, 2, 1, 1, 0, 0]
temps2 = [30, 40, 50, 60]
print(daily_temperatures(temps2)) # [1, 1, 1, 0] (always warmer next day)
temps3 = [30, 60, 90]
print(daily_temperatures(temps3)) # [1, 1, 0]Stos rosnący a malejący: kiedy używać którego
Wybór właściwego kierunku stosu ma kluczowe znaczenie:
- Malejący stos monotoniczny (pop, gdy current > top): odpowiada na zapytania o następny większy element i poprzedni większy element. Jest używany w daily-temperatures, largest-rectangle i trap-rain-water.
- Rosnący stos monotoniczny (pop, gdy current < top): odpowiada na zapytania o następny mniejszy element i poprzedni mniejszy element. Jest używany przy wyznaczaniu zasięgu cen akcji oraz liczby widocznych osób w kolejce.
Proszę pamiętać: element powodujący wykonanie pop jest odpowiedzią na zapytanie dotyczące zdjętego elementu — jest to następny większy albo następny mniejszy element, zależnie od utrzymywanego niezmiennika.
# Summary: which stack type for which query?
queries = {
'Next Greater Element': 'Decreasing stack (pop when new > top)',
'Next Smaller Element': 'Increasing stack (pop when new < top)',
'Previous Greater Element': 'Decreasing stack (answer = top before push)',
'Previous Smaller Element': 'Increasing stack (answer = top before push)',
}
for query, approach in queries.items():
print(f'{query}:\n => {approach}\n')
# Mnemonic:
# NGE/PGE => decreasing stack (we pop smaller elements, finding their next/prev larger)
# NSE/PSE => increasing stack (we pop larger elements, finding their next/prev smaller)Cykliczny następny większy element
Problem Następny większy element II (LeetCode 503): mając tablicę cykliczną (z zawijaniem na początku), należy znaleźć następny większy element. Sztuczka polega na dwukrotnym przetworzeniu tablicy przez podwojenie zakresu indeksów: iterujemy od 0 do 2n-1, używając index % n do zawijania indeksów. Wykonujemy push tylko dla indeksów od 0 do n-1 (w pierwszym przebiegu), aby nie zliczać elementów dwukrotnie.
Alternatywnie w drugim przebiegu można przetwarzać tablicę bez wykonywania push dla nowych indeksów — tylko pop. Obsługuje to prawidłowo wyszukiwanie cykliczne bez faktycznego kopiowania tablicy, zachowując zużycie pamięci O(n).
def next_greater_element_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
idx = stack.pop()
result[idx] = nums[i % n]
if i < n:
stack.append(i) # only push real indices (0..n-1)
return result
print(next_greater_element_circular([1, 2, 1])) # [2, -1, 2]
print(next_greater_element_circular([1, 2, 3, 4, 3])) # [2, 3, 4, -1, 4]
print(next_greater_element_circular([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]Problem Stock Span
Problem Stock Span: mając dzienne ceny akcji, należy obliczyć zasięg każdego dnia — liczbę kolejnych wcześniejszych dni, w których cena była mniejsza lub równa dzisiejszej cenie. Jest to w istocie problem poprzedniego większego elementu: zasięg to odległość od bieżącego dnia do najbliższego dnia z ceną ściśle wyższą.
Należy użyć malejącego stosu monotonicznego. Podczas przetwarzania dnia i wykonujemy pop dla wszystkich dni, dla których cena ≤ current. Zasięg wynosi i - stack[-1], jeśli stos nie jest pusty, albo i + 1, jeśli jest pusty (cena jest najwyższa do tej pory). Następnie wykonujemy push i.
def stock_span(prices):
spans = []
stack = [] # indices of prices forming decreasing sequence
for i, price in enumerate(prices):
while stack and prices[stack[-1]] <= price:
stack.pop()
span = i - stack[-1] if stack else i + 1
spans.append(span)
stack.append(i)
return spans
prices = [100, 80, 60, 70, 60, 75, 85]
print('Prices:', prices)
print('Spans: ', stock_span(prices)) # [1, 1, 1, 2, 1, 4, 6]
# Verification for day 5 (price=75): prev higher is day 1 (80), span = 5-1 = 4
# Day 6 (price=85): prev higher is day 0 (100), span = 6-0 = 6Stos monotoniczny dla widocznych osób w kolejce
Problem Liczba widocznych osób w kolejce: osoby stoją w kolejce, a każda z nich ma określony wzrost. Osoba i może widzieć osobę j (j > i), jeśli wszystkie osoby znajdujące się między nimi są niższe od obu tych osób. Wykorzystuje się tu malejący stos monotoniczny.
Przetwarzamy osoby od prawej do lewej. Utrzymujemy malejący stos wzrostów. Dla każdej osoby obliczamy, ile osób może ona widzieć: zdejmujemy wszystkie niższe osoby (są widoczne, ale później zasłonięte), a następnie dodajemy 1, jeśli po tej operacji stos nie jest pusty (pierwsza wyższa osoba również jest widoczna). Całość działa w czasie O(n), ponieważ każda osoba jest dodawana do stosu i zdejmowana z niego co najwyżej raz.
def visible_people(heights):
n = len(heights)
result = [0] * n
stack = [] # decreasing monotonic stack (heights)
for i in range(n - 1, -1, -1): # right to left
count = 0
while stack and stack[-1] < heights[i]:
stack.pop()
count += 1 # can see this shorter person
if stack:
count += 1 # can see the first person >= heights[i]
result[i] = count
stack.append(heights[i])
return result
heights = [10, 6, 8, 5, 11, 9]
print('Heights:', heights)
print('Visible:', visible_people(heights)) # [3, 1, 2, 1, 1, 0]Gwarancja O(n): dlaczego każdy element jest dodawany i zdejmowany co najwyżej raz
Gwarancja czasu O(n) dla algorytmów wykorzystujących stos monotoniczny wynika z prostego argumentu amortyzacyjnego: każdy element jest dodawany do stosu dokładnie raz i zdejmowany z niego co najwyżej raz. Żaden element nie może zostać dodany ani zdjęty więcej niż raz. W związku z tym łączna liczba operacji push + pop w całej pętli wynosi najwyżej 2n, co daje łączny czas pracy O(n), mimo że zagnieżdżona pętla while może sugerować O(n²).
Umiejętność przedstawienia tej analizy amortyzacyjnej jest ważna podczas rozmów rekrutacyjnych. Pętla while nie wykonuje się n razy w każdej iteracji — działa tylko tak długo, aby zdjąć oczekujące elementy, a po zdjęciu elementy te znikają już na zawsze.
def next_greater_instrumented(nums):
result = [-1] * len(nums)
stack = []
pushes = pops = 0
for i in range(len(nums)):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
pops += 1
stack.append(i)
pushes += 1
print(f'n={len(nums)}, pushes={pushes}, pops={pops}')
print(f'Total operations = {pushes + pops} <= 2n = {2*len(nums)}')
return result
import random
nums = random.sample(range(1000), 100)
next_greater_instrumented(nums)
# Confirm: total operations always <= 2nRozpoznawanie problemów ze stosem monotonicznym
Problem prawdopodobnie wymaga użycia stosu monotonicznego, jeśli pyta o najbliższy większy/mniejszy element, zasięg cen, widoczne elementy w szeregu albo pola oparte na histogramie. Proszę szukać takich słów kluczowych i schematów: dla każdego elementu należy znaleźć odpowiedź pochodzącą od najbliższego właściwego elementu w jednym z kierunków (w lewo lub w prawo).
Jeśli rozwiązanie brutalne przeszukuje elementy w lewo lub w prawo od każdego elementu (O(n²)), należy zastąpić to przeszukiwanie stosem monotonicznym. Stos „zapamiętuje” kandydatów na odpowiedzi, odrzuca nieistotnych kandydatów i zdejmuje właściwą odpowiedź dokładnie w chwili, gdy jest potrzebna.
# Monotonic stack problem recognition guide
patterns = [
('Next/previous greater element', 'Decreasing stack; answer found on pop'),
('Next/previous smaller element', 'Increasing stack; answer found on pop'),
('Days until warmer/colder', 'Stack of indices; answer = i - j'),
('Stock span', 'Decreasing stack; span = i - prev larger idx'),
('Largest rectangle in histogram', 'Increasing stack; area computed on pop'),
('Trapping rain water', 'Decreasing stack or two-pointer'),
('Sliding window maximum', 'Decreasing deque of indices'),
]
print('Monotonic Stack / Deque Pattern Guide:')
print('='*60)
for problem, approach in patterns:
print(f'Problem: {problem}')
print(f' Approach: {approach}')
print()Szybki test
Proszę sprawdzić swoją wiedzę na temat zagadnień z kursu Data Structures & Algorithms — Coding Interview Prep omawianych w tej lekcji.
Podsumowanie lekcji
W tej lekcji poznali Państwo następujące zagadnienia: stos monotoniczny utrzymuje rosnący lub malejący porządek, zdejmując przed wykonaniem push elementy naruszające niezmiennik, stos malejący służy do znajdowania następnego/poprzedniego większego elementu, a stos rosnący — następnego/poprzedniego mniejszego elementu oraz każdy element jest dodawany i zdejmowany co najwyżej raz, co daje łączny czas O(n), a nie O(n²). Następnie zastosujemy stos monotoniczny do znalezienia największego prostokąta w histogramie.
Często zadawane pytania
Czy lekcja „Stos monotoniczny: rosnący a malejący” jest bezpłatna?
Tak — pełny tekst „Stos monotoniczny: rosnący a malejący” 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 DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Stos monotoniczny: rosnący a malejący”?
Utrzymywać stos rosnący lub malejący, aby efektywnie odpowiadać na zapytania o następny większy i poprzedni mniejszy element w czasie O(n) Ćwiczysz DSA 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ąć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA 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 1 z 4.
Ile czasu zajmuje lekcja „Stos monotoniczny: rosnący a malejący”?
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 DSA Interview Prep?
Tak. Każda lekcja DSA 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
- Stos monotoniczny: rosnący a malejący
- Największy prostokąt w histogramie
- Maksimum w oknie przesuwnym za pomocą monotonicznej kolejki dwustronnej
- Trapping Rain Water: stos i dwa wskaźniki