Wzorzec stosu monotonicznego
Zastosują Państwo stos monotoniczny do rozwiązania zadań daily-temperatures, largest-rectangle-in-histogram i next-greater-element w O(n).
Wzorzec stosu monotonicznego to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 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.
Czym jest stos monotoniczny
Stos monotoniczny to stos, który utrzymuje uporządkowany niezmiennik swoich elementów. Rosnący stos monotoniczny zawiera elementy rosnące od dołu do góry, natomiast malejący stos monotoniczny zawiera elementy malejące od dołu do góry. Gdy nowy element narusza niezmiennik, elementy są zdejmowane ze stosu do chwili jego przywrócenia, a następnie nowy element zostaje umieszczony na stosie.
Ten prosty mechanizm umożliwia udzielanie odpowiedzi w czasie O(n) na zapytania o „najbliższy większy element” i „najbliższy mniejszy element”, które w naiwnym rozwiązaniu wymagałyby zagnieżdżonych pętli o złożoności O(n²).
# Build a monotonically increasing stack from [3,1,2,5,4]
nums = [3, 1, 2, 5, 4]
stack = []
for n in nums:
while stack and stack[-1] > n:
stack.pop() # remove elements that violate increasing order
stack.append(n)
print('stack:', stack)Następny większy element (LeetCode 496)
Dla każdego elementu należy znaleźć pierwszy element po jego prawej stronie, który jest od niego ściśle większy. Rozwiązanie siłowe o złożoności O(n²) przeszukuje prawą stronę od każdej pozycji. Podejście ze stosem monotonicznym polega na utrzymywaniu malejącego stosu indeksów. Po napotkaniu większego elementu zdejmujemy wszystkie mniejsze indeksy — ich „następnym większym elementem” jest bieżący element. Pozostałe indeksy nie mają następnego większego elementu (wynik wynosi -1).
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, decreasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
j = stack.pop()
result[j] = val
stack.append(i)
return result
print(nextGreaterElement([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
print(nextGreaterElement([1, 3, 2, 4])) # [3, 4, 4, -1]Następny większy element w tablicy cyklicznej
LeetCode 503 „Next Greater Element II”: ten sam problem, ale tablica jest traktowana jako cykliczna. Po dotarciu do końca należy wrócić na początek i kontynuować sprawdzanie. Sztuczka polega na dwukrotnym przejściu przez tablicę (indeksy od 0 do 2n-1) i użyciu i % n do uzyskania indeksu w oryginalnej tablicy. Aby uniknąć wielokrotnego przetwarzania, należy umieszczać na stosie tylko indeksy z zakresu [0, n-1].
def nextGreaterElements(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
j = stack.pop()
result[j] = nums[i % n]
if i < n:
stack.append(i)
return result
print(nextGreaterElements([1, 2, 1])) # [2, -1, 2]
print(nextGreaterElements([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]Temperatury dobowe: pełne rozwiązanie
Powrót do LeetCode 739: ile dni trzeba czekać od każdego dnia na wyższą temperaturę? Stos monotoniczny przechowuje indeksy dni, których temperatury są ułożone w kolejności malejącej. Po znalezieniu cieplejszego dnia i zdejmujemy ze stosu wszystkie indeksy j chłodniejszych dni i zapisujemy result[j] = i - j. Dni pozostałe na stosie nie doczekały się cieplejszego dnia, więc ich wynik pozostaje równy 0.
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices, decreasing temperatures
for i, t in enumerate(temperatures):
while stack and temperatures[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(dailyTemperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]Poprzedni mniejszy element
Zapytanie o „poprzedni mniejszy element” brzmi: jaka jest najbliższa mniejsza wartość po lewej stronie każdego elementu? Należy użyć rosnącego stosu monotonicznego i przetwarzać elementy od lewej do prawej. Przed umieszczeniem indeksu i na stosie jego wierzchołek wskazuje poprzedni mniejszy element, ponieważ wszystkie elementy większe od nums[i] zostały już usunięte podczas wcześniejszych operacji dodawania, które uruchomiły usuwanie większych elementów.
def previousSmallerElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, increasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] >= val:
stack.pop()
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
print(previousSmallerElement([4, 5, 2, 10, 8])) # [-1, 4, -1, 2, 2]
print(previousSmallerElement([3, 1, 2])) # [-1, -1, 1]Największy prostokąt w histogramie
LeetCode 84 „Largest Rectangle in Histogram”: rosnący stos monotoniczny indeksów. Dla każdego słupka zdejmujemy wszystkie słupki wyższe od bieżącego. Dla każdego zdjętego słupka h jego prawą granicą jest bieżący indeks i, a lewą granicą jest nowy wierzchołek stosu + 1 (lub 0, jeśli stos jest pusty). Pole = h × (prawa granica - lewa granica). Na końcu należy dodać wartownika o wysokości 0, aby wymusić zdjęcie wszystkich pozostałych słupków.
def largestRectangleArea(heights):
heights = heights + [0] # sentinel
stack = [] # indices, increasing heights
result = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0
width = i - left
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2, 1, 5, 6, 2, 3])) # 10
print(largestRectangleArea([2, 4])) # 4
print(largestRectangleArea([1])) # 1Maksymalny prostokąt (LeetCode 85)
LeetCode 85 „Maximal Rectangle” rozszerza problem histogramu na dwuwymiarową macierz binarną. Dla każdego wiersza obliczamy skumulowane wysokości słupków: jeśli matrix[row][col] == '1', wysokość jest liczbą kolejnych jedynek powyżej tej komórki i włącznie z nią. Następnie dla tablicy wysokości każdego wiersza stosujemy algorytm „największego prostokąta w histogramie”. Złożoność czasowa: O(m × n) dla macierzy m×n.
def maximalRectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
result = 0
def largest_in_hist(h):
h = h + [0]
stack, best = [], 0
for i, val in enumerate(h):
while stack and h[stack[-1]] > val:
height = h[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
for row in matrix:
for j, cell in enumerate(row):
heights[j] = heights[j] + 1 if cell == '1' else 0
result = max(result, largest_in_hist(heights[:]))
return result
m = [['1','0','1','0','0'],['1','0','1','1','1'],
['1','1','1','1','1'],['1','0','0','1','0']]
print(maximalRectangle(m)) # 6Zbieranie wody deszczowej: podejście ze stosem
LeetCode 42 „Trapping Rain Water” ze stosem: utrzymujemy malejący stos indeksów. Po napotkaniu wyższego słupka powstaje zagłębienie. Zdejmujemy dno zagłębienia, a następnie obliczamy szerokość wody jako (current_index - stack_top - 1) i wysokość jako (min(current_bar, new_stack_top_bar) - valley_height). Sumujemy wszystkie wkłady. Złożoność czasowa: O(n), pamięciowa: O(n).
def trap(height):
stack = []
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = stack.pop()
if not stack:
break
left = stack[-1]
width = i - left - 1
bounded_h = min(h, height[left]) - height[bottom]
water += width * bounded_h
stack.append(i)
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap([4,2,0,3,2,5])) # 9Rozpoznawanie problemów dla stosu monotonicznego
Sygnały wskazujące, że właściwym narzędziem jest stos monotoniczny: problem wymaga znalezienia następnego lub poprzedniego większego/mniejszego elementu, odpowiedź dla każdego elementu zależy od elementów w określonym kierunku albo naiwne rozwiązanie O(n²) polega na przeszukiwaniu lewej lub prawej strony dla każdego elementu. Stos przechowuje kandydatów, którzy mogą być odpowiedziami dla przyszłych elementów, i odrzuca ich, gdy tylko pojawi się lepszy kandydat.
Zawsze należy z góry określić: stos rosnący (dla następnego/poprzedniego mniejszego elementu) czy malejący (dla następnego/poprzedniego większego elementu), a także kierunek przetwarzania.
Zamortyzowana analiza O(n)
Algorytmy ze stosem monotonicznym początkowo mogą wyglądać na rozwiązania O(n log n) lub O(n²), ponieważ pętla while znajduje się wewnątrz pętli for. Jednak każdy element jest umieszczany na stosie najwyżej raz i zdejmowany najwyżej raz. Łączna liczba operacji umieszczania wynosi n, a łączna liczba operacji zdejmowania również wynosi najwyżej n. Zatem we wszystkich iteracjach wykonujemy łącznie 2n operacji — zamortyzowana złożoność wynosi O(n), a nie O(n²).
# Count total pushes and pops for n=1000
n = 1000
nums = list(range(n, 0, -1)) # worst case for decreasing stack
stack = []
pushes = pops = 0
for val in nums:
while stack and stack[-1] < val:
stack.pop()
pops += 1
stack.append(val)
pushes += 1
print(f'n={n}, pushes={pushes}, pops={pops}, total={pushes+pops}')
# Total <= 2*nPodsumowanie: wybór niezmiennika stosu monotonicznego
Kierunek stosu należy wybrać na podstawie rodzaju zapytania. Dla następnego większego elementu używamy stosu malejącego — zdejmujemy elementy, gdy bieżący element jest większy. Dla następnego mniejszego elementu używamy stosu rosnącego — zdejmujemy elementy, gdy bieżący element jest mniejszy. Dla największego prostokąta używamy stosu rosnącego i zdejmujemy elementy, gdy pojawi się niższy słupek. Dla maksimum w przesuwanym oknie używamy malejącego deque i usuwamy elementy z obu końców.
Zapisanie niezmiennika w komentarzu przed rozpoczęciem kodowania ułatwia zrozumienie logiki i przyspiesza debugowanie.
Szybkie sprawdzenie
Proszę sprawdzić swoje zrozumienie zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji poznano: stos monotoniczny utrzymuje uporządkowany niezmiennik, usuwając elementy, które go naruszają, przed umieszczeniem nowego elementu, stosy malejące odpowiadają na zapytania o następny większy element, a stosy rosnące — o następny mniejszy element oraz łączna złożoność czasowa wynosi zamortyzowane O(n), ponieważ każdy element jest umieszczany na stosie i zdejmowany najwyżej raz. Następnie zaimplementujemy kolejki za pomocą stosów oraz stosy za pomocą kolejek.
Często zadawane pytania
Czy lekcja „Wzorzec stosu monotonicznego” jest bezpłatna?
Tak — pełny tekst „Wzorzec stosu monotonicznego” 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 „Wzorzec stosu monotonicznego”?
Zastosują Państwo stos monotoniczny do rozwiązania zadań daily-temperatures, largest-rectangle-in-histogram i next-greater-element w O(n). Ć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 3 z 4.
Ile czasu zajmuje lekcja „Wzorzec stosu monotonicznego”?
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
- Implementacja stosu i zastosowania
- Implementacja kolejki i deque
- Wzorzec stosu monotonicznego
- Wzajemna symulacja stosu i kolejki