Największy prostokąt w histogramie
Używać stosu monotonicznego do śledzenia lewych granic i obliczać w jednym przebiegu prostokąt o maksymalnym polu, który mieści się w histogramie
Największy prostokąt w histogramie 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: największy prostokąt w histogramie
Problem Największy prostokąt w histogramie (LeetCode 84) przedstawia tablicę nieujemnych liczb całkowitych reprezentujących wysokości słupków histogramu, gdzie każdy słupek ma szerokość 1. Należy znaleźć pole największego prostokąta, który można utworzyć w histogramie. Prostokąt musi obejmować sąsiadujące słupki, a jego wysokość jest ograniczona przez najniższy obejmowany słupek.
Podejście brutalne: dla każdej pary (i, j) obliczamy minimalną wysokość w przedziale [i, j] i mnożymy ją przez (j - i + 1). Złożoność wynosi O(n³) albo O(n²) przy wcześniej obliczonych minimach — to zbyt wolno. Rozwiązanie ze stosem monotonicznym działa w czasie O(n).
# Example: heights = [2, 1, 5, 6, 2, 3]
# Rectangles:
# width=1, height=6 at index 3 => area=6
# width=2, height=5 at indices 2-3 => area=10 (maximum!)
# width=6, height=1 across all => area=6
# width=3, height=2 at indices 2-4 => area=6
heights = [2, 1, 5, 6, 2, 3]
print('Heights:', heights)
print('Expected max area: 10 (bars of height 5 and 6, width 2)')
# Brute force for small inputs:
def brute_force(heights):
n = len(heights)
max_area = 0
for i in range(n):
min_h = heights[i]
for j in range(i, n):
min_h = min(min_h, heights[j])
max_area = max(max_area, min_h * (j - i + 1))
return max_area
print('Brute force answer:', brute_force(heights)) # 10Kluczowa obserwacja: co ogranicza prostokąt danego słupka?
Dla każdego słupka i o wysokości h największy prostokąt, w którym może on być minimum, rozciąga się w lewo aż do pierwszego słupka niższego niż h oraz w prawo aż do pierwszego słupka niższego niż h. Szerokość wynosi right_boundary - left_boundary - 1, a pole to h × width.
Takie ujęcie zmienia problem: dla każdego słupka należy znaleźć jego poprzedni mniejszy element (PSE) i następny mniejszy element (NSE). Są to dokładnie wartości obliczane przez rosnący stos monotoniczny. W chwili, gdy zdejmujemy słupek i (ponieważ znaleziono niższy słupek), bieżący słupek jest jego NSE, a wierzchołek stosu po zdjęciu jest jego PSE.
heights = [2, 1, 5, 6, 2, 3]
n = len(heights)
# Find PSE and NSE for each bar
pse = [-1] * n # index of previous smaller element
nse = [n] * n # index of next smaller element (default: beyond array)
# PSE
stack = []
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
pse[i] = stack[-1] if stack else -1
stack.append(i)
# NSE
stack = []
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
nse[i] = stack[-1] if stack else n
stack.append(i)
max_area = 0
for i in range(n):
width = nse[i] - pse[i] - 1
area = heights[i] * width
print(f'Bar {i} (h={heights[i]}): PSE={pse[i]}, NSE={nse[i]}, width={width}, area={area}')
max_area = max(max_area, area)
print('Max area:', max_area)Rozwiązanie jednoprzebiegowe ze stosem monotonicznym
Powyższe podejście dwuprzebiegowe działa, ale można je połączyć w jeden przebieg. Przetwarzamy słupki od lewej do prawej, używając rosnącego stosu monotonicznego. Gdy słupek i jest niższy od wierzchołka stosu, zdejmujemy wierzchołek stosu — wysokość zdjętego słupka jest wysokością prostokąta, jego prawą granicą jest i, a lewą granicą jest nowy wierzchołek stosu + 1.
Standardowa sztuczka polega na dodaniu na końcu tablicy heights wartownika 0. Dzięki temu wszystkie słupki zostaną zdjęte ze stosu na końcu, nawet jeśli naturalnie nie pojawi się niższy słupek. Bez wartownika potrzebna byłaby faza porządkowania pozostałych elementów po zakończeniu pętli.
def largest_rectangle(heights):
stack = [] # monotonic increasing: indices of bars
max_area = 0
heights = heights + [0] # sentinel: forces all bars to be popped
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()] # height of the rectangle
width = i if not stack else i - stack[-1] - 1 # left boundary
max_area = max(max_area, height * width)
stack.append(i)
return max_area
print(largest_rectangle([2, 1, 5, 6, 2, 3])) # 10
print(largest_rectangle([2, 4])) # 4
print(largest_rectangle([1, 1])) # 2
print(largest_rectangle([0, 9])) # 9
print(largest_rectangle([6, 7, 5, 2, 4, 5, 9, 3])) # 16Śledzenie działania algorytmu jednoprzebiegowego
Prześledźmy krok po kroku tablicę [2, 1, 5, 6, 2, 3, 0] (z wartownikiem):
- i=0, h=2: push 0. Stos: [0]
- i=1, h=1: pop 0 (h=2, width=1, area=2). Stos pusty, push 1. Stos: [1]
- i=2, h=5: 5>1, push 2. Stos: [1,2]
- i=3, h=6: 6>5, push 3. Stos: [1,2,3]
- i=4, h=2: pop 3 (h=6,width=4-2-1=1,area=6), pop 2 (h=5,width=4-1-1=2,area=10★), 2>1 stop. Push 4. Stos: [1,4]
- i=5, h=3: 3>2, push 5. Stos: [1,4,5]
- i=6, wartownik h=0: pop wszystkich elementów, obliczając pola...
def largest_rectangle_trace(heights):
stack = []
max_area = 0
hs = heights + [0]
for i, h in enumerate(hs):
while stack and hs[stack[-1]] > h:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
area = hs[top] * w
print(f' Pop bar {top} (h={hs[top]}): width={w}, area={area}', end='')
if area > max_area:
max_area = area
print(' *** NEW MAX ***', end='')
print()
print(f'i={i} h={h}: push {i}, stack={[hs[s] for s in stack + [i]]}')
stack.append(i)
print(f'Max area: {max_area}')
return max_area
largest_rectangle_trace([2, 1, 5, 6, 2, 3])Obliczanie szerokości: dlaczego i - stack[-1] - 1?
Gdy zdejmujemy ze stosu słupek j, wiemy, że: prawą granicą prostokąta słupka j jest i (pierwszy słupek po prawej stronie niższy od j). Lewą granicą jest słupek znajdujący się bezpośrednio pod j na stosie po wykonaniu pop — oznaczmy go k. Szerokość wynosi więc i - k - 1 (słupki od k+1 do i-1 włącznie).
Jeśli po wykonaniu pop stos jest pusty, prostokąt słupka j rozciąga się aż do lewej krawędzi (indeks 0). Szerokość wynosi po prostu i (indeksy od 0 do i-1, z których wszystkie mają wysokość co najmniej heights[j]). Jest to przypadek szczególny width = i if not stack else i - stack[-1] - 1.
# Illustrating left/right boundary logic
heights = [1, 3, 5, 2]
# After processing with stack:
# When we pop bar 2 (h=5) at i=3 (h=2):
# stack after pop = [0, 1] => left boundary = 1+1=2, right=3-1=2 => width=1
# When we pop bar 1 (h=3) at i=3 (h=2):
# stack after pop = [0] => left boundary = 0+1=1, right=3-1=2 => width=2
# etc.
def compute_boundaries(heights):
hs = heights + [0]
stack = []
for i, h in enumerate(hs):
while stack and hs[stack[-1]] > h:
top = stack.pop()
if stack:
left = stack[-1] + 1
width = i - stack[-1] - 1
else:
left = 0
width = i
print(f'Bar {top} (h={hs[top]}): extends from {left} to {i-1}, width={width}')
stack.append(i)
compute_boundaries([2, 1, 5, 6, 2, 3])Maksymalny prostokąt w macierzy binarnej
Maksymalny prostokąt (LeetCode 85) rozszerza problem histogramu na dwuwymiarową macierz binarną. Dla każdego wiersza obliczamy wysokość kolejnych jedynek znajdujących się nad każdą komórką. Tworzy to histogram dla danego wiersza. Następnie stosujemy algorytm największego prostokąta w histogramie do histogramu każdego wiersza. Odpowiedzią jest największa wartość spośród wyników dla wszystkich wierszy.
W ten sposób problem 2D zostaje sprowadzony do n powtarzanych problemów histogramu 1D. Złożoność czasowa wynosi O(m × n) dla macierzy o m wierszach i n kolumnach — jeden przebieg histogramu na wiersz, a każdy przebieg działa w czasie O(n).
def maximal_rectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
max_area = 0
def hist_max_area(h):
stack, area = [], 0
for i, hh in enumerate(h + [0]):
while stack and h[stack[-1]] > hh:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
area = max(area, h[top] * w)
stack.append(i)
return area
for row in matrix:
for j in range(n):
heights[j] = heights[j] + 1 if row[j] == '1' else 0
max_area = max(max_area, hist_max_area(heights[:]))
return max_area
matrix = [['1','0','1','0','0'],
['1','0','1','1','1'],
['1','1','1','1','1'],
['1','0','0','1','0']]
print(maximal_rectangle(matrix)) # 6Przypadki brzegowe w problemach histogramowych
Ważne przypadki brzegowe:
- Jednakowa wysokość wszystkich słupków: cała tablica tworzy jeden prostokąt; wynik = n × height
- Monotoniczny wzrost: żadne pop nie występuje aż do wartownika; pole ostatniego słupka jest maksymalne
- Pojedynczy słupek: wynik = height[0]
- Słupki o wysokości 0: działają jak naturalne wartowniki, dzieląc histogram na niezależne fragmenty
Wartownik (dodanie 0) na końcu obsługuje przypadek monotonicznego wzrostu, wymuszając zdjęcie wszystkich pozostałych słupków na końcu. Bez niego potrzebna byłaby osobna pętla porządkująca po głównej iteracji.
def largest_rectangle(heights):
stack = []
max_area = 0
heights = heights + [0]
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
max_area = max(max_area, heights[top] * w)
stack.append(i)
return max_area
# Edge cases
print(largest_rectangle([5, 5, 5, 5])) # 20 (all same)
print(largest_rectangle([1, 2, 3, 4, 5])) # 9 (increasing: 3*3)
print(largest_rectangle([5, 4, 3, 2, 1])) # 9 (decreasing: 3*3)
print(largest_rectangle([5])) # 5 (single bar)
print(largest_rectangle([0, 0, 0])) # 0 (all zero)
print(largest_rectangle([3, 0, 3])) # 3 (zero splits)Alternatywa: dziel i zwyciężaj
Problem histogramu można również rozwiązać metodą dziel i zwyciężaj: dzielimy histogram przy słupku o minimalnej wysokości, rekurencyjnie rozwiązujemy obie połowy i porównujemy wynik z prostokątem obejmującym całą szerokość, którego wysokość jest równa minimum. Daje to średnią złożoność O(n log n), ale w najgorszym przypadku O(n) dla posortowanych danych.
Podejście ze stosem monotonicznym jest zdecydowanie lepsze, ponieważ w najgorszym przypadku działa w czasie O(n). Zrozumienie podejścia dziel i zwyciężaj pogłębia jednak intuicję dotyczącą problemu i wyjaśnia, dlaczego słupek o minimalnej wysokości w dowolnym fragmencie zawsze ogranicza prostokąty obejmujące całą jego szerokość.
def largest_rectangle_dc(heights, lo=0, hi=None):
if hi is None:
hi = len(heights) - 1
if lo > hi:
return 0
# Find the index of the minimum height in [lo, hi]
min_idx = lo
for i in range(lo, hi + 1):
if heights[i] < heights[min_idx]:
min_idx = i
# Three options:
# 1. Max rect entirely in left half
# 2. Max rect entirely in right half
# 3. Max rect spanning entire [lo, hi] with height = min
full_width_area = heights[min_idx] * (hi - lo + 1)
left_area = largest_rectangle_dc(heights, lo, min_idx - 1)
right_area = largest_rectangle_dc(heights, min_idx + 1, hi)
return max(full_width_area, left_area, right_area)
print(largest_rectangle_dc([2, 1, 5, 6, 2, 3])) # 10Schemat histogramu: liczba podtablic
Powiązany problem wykorzystujący tę samą technikę stosu: policzenie liczby podtablic w histogramie, w których element minimalny jest równy określonej wartości docelowej. Rozwiązanie polega na obliczeniu PSE i NSE dla każdego słupka, a następnie użyciu wzoru (i - pse[i]) × (nse[i] - i), który zlicza podhistogramy, w których słupek i jest minimum.
Technika „liczba po lewej × liczba po prawej” pojawia się w kilku problemach LeetCode: suma minimów podtablic (907), liczba podciągów o unikatowych znakach oraz problemy wykorzystujące technikę wkładu. Stos monotoniczny oblicza PSE i NSE w czasie O(n), umożliwiając obliczenie wkładu każdego elementu w czasie O(1).
def sum_of_subarray_minimums(arr):
n = len(arr)
pse = [-1] * n # previous strictly smaller element
nse = [n] * n # next smaller or equal element
stack = []
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
pse[i] = stack[-1] if stack else -1
stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
nse[i] = stack[-1] if stack else n
stack.append(i)
MOD = 10**9 + 7
total = 0
for i in range(n):
left_count = i - pse[i] # subarrays where i is leftmost min
right_count = nse[i] - i # subarrays where i is the min
total += arr[i] * left_count * right_count
return total % MOD
print(sum_of_subarray_minimums([3, 1, 2, 4])) # 17
print(sum_of_subarray_minimums([11, 81, 94, 43, 3])) # 444Praktyczne wskazówki dotyczące rozmowy kwalifikacyjnej
Gdy podczas rozmowy kwalifikacyjnej pojawi się zadanie dotyczące histogramu, należy postępować zgodnie z poniższą listą:
- Doprecyzować: czy wysokości mogą wynosić 0? Jaki ma być wynik — pole, indeksy czy liczba?
- Zacząć od rozwiązania siłowego i podać złożoność O(n²) lub O(n³)
- Wspomnieć, że wkład każdego słupka zależy od jego zasięgu w lewo i w prawo, aż do najbliższego niższego słupka
- Przedstawić PSE/NSE → monotoniczny stos → rozwiązanie O(n)
- Wykorzystać sztuczkę z wartownikiem (dodać 0), aby uprościć kod
- Prześledzić mały przykład na tablicy
Częste pytanie dodatkowe: rozszerzyć rozwiązanie do 2D (największy prostokąt). Należy pokazać, że problem można sprowadzić do n problemów histogramowych, z których każdy ma złożoność O(n), co daje łącznie O(m×n).
# Final clean solution for interview
def largest_rectangle_in_histogram(heights):
stack = []
max_area = 0
for i, h in enumerate(heights + [0]): # sentinel forces final pops
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
# Verify all test cases from earlier
test_cases = [
([2, 1, 5, 6, 2, 3], 10),
([6, 7, 5, 2, 4, 5, 9, 3], 16),
([1], 1),
([2, 0, 2], 2),
([], 0),
]
for heights, expected in test_cases:
if not heights:
result = 0
else:
result = largest_rectangle_in_histogram(heights)
status = 'PASS' if result == expected else 'FAIL'
print(f'{status}: {heights} => {result} (expected {expected})')Suma zakresów podtablic i podobne warianty
Technika PSE/NSE ma zastosowanie w kilku zadaniach z LeetCode. Suma zakresów podtablic (2104) wymaga obliczenia sumy (max - min) dla wszystkich podtablic. Jest ona równa (sumie maksimów podtablic) pomniejszonej o (sumę minimów podtablic), przy czym każdą z tych sum można obliczyć za pomocą monotonicznego stosu w czasie O(n). Liczba widocznych osób w kolejce (1944) wykorzystuje stos malejący, w którym każde zdjęcie elementu oznacza naliczenie jednej widocznej osoby. Rozpoznanie tej rodziny problemów polega na zauważeniu pytania „dla każdego elementu: jak daleko może on dominować?” — odpowiedzią zawsze jest PSE/NSE z użyciem monotonicznego stosu.
def sum_subarray_ranges(nums):
n = len(nums)
# Sum of subarray max - sum of subarray min
def contrib(arr, is_max):
# Count contribution of each element as max (or min)
n = len(arr)
left = [0]*n; right = [0]*n
stack = []
for i in range(n):
while stack and (arr[stack[-1]] < arr[i] if is_max else arr[stack[-1]] > arr[i]):
stack.pop()
left[i] = i - (stack[-1] if stack else -1)
stack.append(i)
stack = []
for i in range(n-1, -1, -1):
while stack and (arr[stack[-1]] <= arr[i] if is_max else arr[stack[-1]] >= arr[i]):
stack.pop()
right[i] = (stack[-1] if stack else n) - i
stack.append(i)
return sum(arr[i] * left[i] * right[i] for i in range(n))
return contrib(nums, True) - contrib(nums, False)
print(sum_subarray_ranges([1, 2, 3])) # 4
print(sum_subarray_ranges([1, 3, 3])) # 4
print(sum_subarray_ranges([4, -2, -3, 4, 1])) # 59Szybki test
Sprawdź swoją znajomość zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo, że: dla każdego słupka granice największego zawierającego go prostokąta wyznaczają najbliższe niższe słupki po obu stronach (PSE i NSE), monotoniczny stos rosnący oblicza wszystkie granice PSE/NSE w jednym przebiegu O(n), znajdując je w chwili zdejmowania słupków ze stosu oraz dodanie wartownika 0 gwarantuje zdjęcie ze stosu wszystkich słupków i upraszcza kod do jednej pętli. Następnie wykorzystamy monotoniczną kolejkę dwustronną do rozwiązania problemu maksimum w przesuwającym się oknie w czasie O(n).
Często zadawane pytania
Czy lekcja „Największy prostokąt w histogramie” jest bezpłatna?
Tak — pełny tekst „Największy prostokąt w histogramie” 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 „Największy prostokąt w histogramie”?
Używać stosu monotonicznego do śledzenia lewych granic i obliczać w jednym przebiegu prostokąt o maksymalnym polu, który mieści się w histogramie Ć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 „Największy prostokąt w histogramie”?
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
- 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