Største rektangel i et histogram
Brug en monoton stak til at holde styr på venstre grænser og beregne arealet af det største rektangel, der kan rummes i et histogram, i ét gennemløb.
Største rektangel i et histogram er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 2 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Problem: Største rektangel i et histogram
Problemet Største rektangel i et histogram (LeetCode 84) giver et array af ikke-negative heltal, der repræsenterer søjlehøjderne i et histogram, hvor hver søjle har bredden 1. Find arealet af det største rektangel, der kan dannes i histogrammet. Rektanglet skal spænde over sammenhængende søjler, og dets højde begrænses af den laveste søjle, det dækker.
En udtømmende metode: Beregn for hvert par (i, j) den mindste højde i [i, j], og gang den med (j - i + 1). Det giver O(n³) eller O(n²) med forudberegnede minimumsværdier — hvilket er for langsomt. Løsningen med en monoton stak kører i 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)) # 10Vigtigste indsigt: Hvad begrænser hver søjles rektangel
For hver søjle i med højden h strækker det største rektangel, hvor søjlen kan være minimum, sig mod venstre indtil den første søjle, der er lavere end h, og mod højre indtil den første søjle, der er lavere end h. Bredden er right_boundary - left_boundary - 1, og arealet er h × width.
Det giver en ny formulering af problemet: For hver søjle skal du finde dens forrige mindre element (PSE) og næste mindre element (NSE). Det er præcis det, en monotonisk stigende stak beregner. Når vi fjerner søjle i, fordi en lavere søjle er fundet, er den aktuelle søjle dens NSE, og staktoppen efter fjernelsen er dens 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)Løsning med ét gennemløb og en monoton stak
Løsningen med to gennemløb ovenfor virker, men kan samles i ét gennemløb. Gennemløb søjlerne fra venstre mod højre med en monotonisk stigende stak. Når søjle i er lavere end staktoppen, fjernes staktoppen — den fjernede søjles højde er højden på et rektangel, dens højre grænse er i, og dens venstre grænse er den nye staktop + 1.
Et almindeligt trick er at tilføje en sentinelværdi på 0 i slutningen af heights. Det sikrer, at alle søjler fjernes fra stakken til sidst, selv hvis der ikke naturligt dukker en lavere søjle op. Uden sentinelværdien har du brug for en oprydningsfase efter løkken til de resterende elementer på stakken.
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])) # 16Gennemgang af algoritmen med ét gennemløb
Lad os gennemgå [2, 1, 5, 6, 2, 3, 0] (med sentinelværdi) trin for trin:
- i=0, h=2: læg 0 på stakken. Stak: [0]
- i=1, h=1: fjern 0 (h=2, width=1, area=2). Stakken er tom, læg 1 på stakken. Stak: [1]
- i=2, h=5: 5>1, læg 2 på stakken. Stak: [1,2]
- i=3, h=6: 6>5, læg 3 på stakken. Stak: [1,2,3]
- i=4, h=2: fjern 3 (h=6,width=4-2-1=1,area=6), fjern 2 (h=5,width=4-1-1=2,area=10★), 2>1, stop. Læg 4 på stakken. Stak: [1,4]
- i=5, h=3: 3>2, læg 5 på stakken. Stak: [1,4,5]
- i=6, sentinel h=0: fjern alle elementer, og beregn arealerne...
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])Beregning af bredden: Hvorfor i - stack[-1] - 1?
Når vi fjerner søjle j fra stakken, ved vi, at den højre grænse for søjlens rektangel er i (den første søjle til højre, der er lavere end j). Den venstre grænse er søjlen lige under j i stakken efter fjernelsen — kald den k. Bredden er derfor i - k - 1 (søjlerne fra k+1 til i-1 inklusive).
Hvis stakken er tom efter fjernelsen, strækker j's rektangel sig hele vejen til venstre kant (indeks 0). Bredden er ganske enkelt i (indeksene 0 til i-1, som alle er mindst lige så høje som heights[j]). Dette er specialtilfældet 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])Maksimalt rektangel i en binær matrix
Maksimalt rektangel (LeetCode 85) udvider histogramproblemet til en 2D-binær matrix. For hver række beregner du højden af sammenhængende 1-taller over hver celle. Det danner et histogram for den pågældende række. Anvend algoritmen for største rektangel i et histogram på hver rækkes histogram. Det samlede maksimum på tværs af alle rækker er svaret.
Det reducerer et 2D-problem til n gentagne 1D-histogramproblemer. Tidskompleksiteten er O(m × n) for en matrix med m rækker og n kolonner — ét histogramgennemløb pr. række, hvor hvert gennemløb er 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)) # 6Kanttilfælde i histogramproblemer
Vigtige kanttilfælde, der skal håndteres:
- Alle søjler har samme højde: Hele arrayet danner ét rektangel; svaret = n × height
- Monotont stigende: Der sker ingen fjernelse før sentinelværdien; den sidste søjles areal er det største
- En enkelt søjle: svaret = height[0]
- Søjler med højden 0: De fungerer som naturlige sentinelværdier, der opdeler histogrammet i uafhængige segmenter
Sentinelværdien (ved at tilføje 0) til sidst håndterer det monotont stigende tilfælde ved at tvinge alle resterende søjler til at blive fjernet til sidst. Uden den har du brug for en separat oprydningsløkke efter hovedgennemløbet.
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)Alternativ med del-og-hersk
Histogramproblemet kan også løses med del-og-hersk: Del ved søjlen med den mindste højde, løs rekursivt hver halvdel, og sammenlign med rektanglet, der spænder over hele bredden med den mindste højde. Det giver O(n log n) i gennemsnit, men O(n²) i værste fald for sorterede input.
Metoden med den monotone stak er entydigt bedre med O(n) i værste fald. Men en forståelse af del-og-hersk-metoden giver en dybere forståelse af problemet og forklarer, hvorfor søjlen med den mindste højde i et segment altid er den begrænsende faktor for rektangler i fuld bredde.
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])) # 10Histogrammønster: Antal delsekvenser
Et beslægtet problem, der bruger den samme stakteknik: Tæl antallet af delsekvenser i et histogram, hvor minimumselementet er lig med et bestemt mål. Det løses ved at beregne PSE og NSE for hver søjle og derefter bruge formlen (i - pse[i]) × (nse[i] - i), som tæller delhistogrammer, hvor søjle i er minimum.
Teknikken med antal til venstre × antal til højre optræder i flere LeetCode-problemer: summen af delsekvensernes minimumsværdier (907), optælling af delstrenge med kun unikke tegn og problemer med bidragsmetoden. Den monotone stak beregner PSE og NSE i O(n), så hvert elements bidrag kan beregnes i 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])) # 444Praktiske tips til jobsamtalen
Når du møder et histogramproblem til en jobsamtale, skal du følge denne tjekliste:
- Afklar: Kan højder være 0? Hvad er resultatet – areal, indekser eller antal?
- Start med en udtømmende løsning, og angiv en kompleksitet på O(n²) eller O(n³)
- Nævn, at hver søjles bidrag afhænger af, hvor langt den strækker sig mod venstre og højre frem til den nærmeste lavere søjle
- Introducer PSE/NSE → monoton stak → O(n)-løsning
- Brug tricket med en vagtværdi (tilføj 0) for at forenkle koden
- Følg et lille eksempel på tavlen
Et almindeligt opfølgende spørgsmål er at udvide til 2D (største rektangel). Demonstrér, at du kan reducere det til n histogramproblemer, som hver tager O(n), så den samlede kompleksitet bliver 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})')Sum af delarrayintervaller og lignende varianter
PSE/NSE-teknikken kan generaliseres til flere LeetCode-problemer. Summen af delarrayintervaller (2104) beder om summen af (maksimum - minimum) på tværs af alle delarrays. Det svarer til (summen af delarraymaksima) minus (summen af delarrayminima), hvor hver del beregnes med en monoton stak i O(n). Antallet af synlige personer i en kø (1944) bruger en faldende stak, hvor hver fjernelse tæller en synlig person. Du genkender denne familie af problemer ved at lægge mærke til formuleringen "for hvert element, hvor langt kan det dominere?" — svaret er altid PSE/NSE med en monoton stak.
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])) # 59Hurtigt tjek
Afprøv din forståelse af begreberne Data Structures & Algorithms — Coding Interview Prep fra denne lektion.
Opsummering af lektionen
I denne lektion lærte du: For hver søjle har det største rektangel, der kan dannes, grænser ved den nærmeste lavere søjle på hver side (PSE og NSE), en monoton stigende stak beregner alle PSE/NSE-grænser i én O(n)-gennemløbning ved at finde begge dele, når søjler fjernes fra stakken, og tilføjelse af en vagtværdi på 0 sikrer, at alle søjler fjernes fra stakken, så koden kan forenkles til én enkelt løkke. Nu bruger vi den monotone deque til at finde maksimum i et glidende vindue i O(n).
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Største rektangel i et histogram” gratis?
Ja — hele teksten til “Største rektangel i et histogram” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Største rektangel i et histogram”?
Brug en monoton stak til at holde styr på venstre grænser og beregne arealet af det største rektangel, der kan rummes i et histogram, i ét gennemløb. Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 2 af 4.
Hvor lang tid tager lektionen “Største rektangel i et histogram”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Monoton stak: Stigende eller faldende
- Største rektangel i et histogram
- Maksimum i skydevindue med en monoton deque
- Opsamling af regnvand: Stak og to pegere