PricingLoginStart free
DSA Interview Prep · Les

Grootste rechthoek in een histogram

Gebruik een monotone stack om linkergrenzen bij te houden en bereken in één doorgang de rechthoek met de grootste oppervlakte die in een histogram past.

Les 2 van 413 stappen

Grootste rechthoek in een histogram is een gratis DSA Interview Prep-les op CoddyKit. Dit is les 2 van 4. Je kunt 3 lessen uit dit leerpad gratis volledig lezen — daarna ontgrendelt CoddyKit PRO alle lessen, plus praktische oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject DSA Interview Prep. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus DSA Interview Prep bevat in totaal 4 lessen.

Probleem: grootste rechthoek in een histogram

Het probleem Grootste rechthoek in een histogram (LeetCode 84) geeft een array met niet-negatieve gehele getallen die de hoogten van staven in een histogram voorstellen, waarbij elke staaf breedte 1 heeft. Zoek het oppervlak van de grootste rechthoek die binnen het histogram kan worden gevormd. De rechthoek moet aaneengesloten staven omvatten en de hoogte wordt beperkt door de kortste staaf die hij omvat.

Een uitputtende aanpak: bereken voor elk paar (i, j) de minimale hoogte in [i, j] en vermenigvuldig die met (j - i + 1). Dit kost O(n³), of O(n²) met vooraf berekende minimumwaarden — te langzaam. De oplossing met een monotone stapel werkt in 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))  # 10

Belangrijk inzicht: wat begrenst de rechthoek van elke staaf?

Voor elke staaf i met hoogte h loopt de grootste rechthoek waarvan die staaf het minimum kan zijn naar links tot de eerste staaf die korter is dan h, en naar rechts tot de eerste staaf die korter is dan h. De breedte is right_boundary - left_boundary - 1 en het oppervlak is h × width.

Dit herformuleert het probleem: vind voor elke staaf het vorige kleinere element (PSE) en het volgende kleinere element (NSE). Dat is precies wat een monotone toenemende stapel berekent. Op het moment dat we staaf i van de stapel halen (omdat er een kortere staaf is gevonden), is de huidige staaf zijn NSE en is de top van de stapel na het verwijderen zijn 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)

Oplossing in één doorgang met een monotone stapel

De aanpak in twee doorgangen hierboven werkt, maar kan worden samengevoegd tot één doorgang. Verwerk de staven van links naar rechts met een monotone toenemende stapel. Wanneer staaf i korter is dan de bovenste staaf op de stapel, haal je die bovenste staaf van de stapel — de hoogte van de verwijderde staaf is de hoogte van een rechthoek, de rechtergrens is i en de linkergrens is de nieuwe top van de stapel + 1.

Een standaardtruc is om aan het einde van heights een wachtwaarde 0 toe te voegen. Zo worden alle staven aan het einde van de stapel verwijderd, ook als er van nature geen kortere staaf verschijnt. Zonder de wachtwaarde heb je na de lus een afzonderlijke opschoningsfase nodig voor de overgebleven elementen op de stapel.

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

Het algoritme in één doorgang stap voor stap volgen

We volgen [2, 1, 5, 6, 2, 3, 0] (met wachtwaarde) stap voor stap:

  • i=0, h=2: push 0. Stack: [0]
  • i=1, h=1: pop 0 (h=2, width=1, area=2). Stack is leeg, push 1. Stack: [1]
  • i=2, h=5: 5>1, push 2. Stack: [1,2]
  • i=3, h=6: 6>5, push 3. Stack: [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. Stack: [1,4]
  • i=5, h=3: 3>2, push 5. Stack: [1,4,5]
  • i=6, wachtwaarde h=0: verwijder alles van de stapel en bereken de oppervlakken...
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])

Breedteberekening: waarom i - stack[-1] - 1?

Wanneer we staaf j van de stapel halen, weten we het volgende: de rechtergrens van de rechthoek van j is i (de eerste staaf rechts die korter is dan j). De linkergrens is de staaf die na het verwijderen direct onder j op de stapel staat — noem die k. De breedte is daarom i - k - 1 (de staven van k+1 tot en met i-1).

Als de stapel na het verwijderen leeg is, loopt de rechthoek van j helemaal door tot de linkerrand (index 0). De breedte is dan eenvoudigweg i (de indexen 0 tot en met i-1, die allemaal minstens zo hoog zijn als heights[j]). Dit is het speciale geval 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])

Maximale rechthoek in een binaire matrix

Maximale rechthoek (LeetCode 85) breidt het histogramprobleem uit naar een tweedimensionale binaire matrix. Bereken voor elke rij de hoogte van de opeenvolgende enen boven elke cel. Zo ontstaat voor die rij een histogram. Pas op het histogram van elke rij het algoritme voor de grootste rechthoek in een histogram toe. Het grootste resultaat over alle rijen is het antwoord.

Hiermee wordt een tweedimensionaal probleem herleid tot m herhaalde eendimensionale histogramproblemen. De tijdcomplexiteit is O(m × n) voor een matrix met m rijen en n kolommen — één doorgang door het histogram per rij, waarbij elke doorgang O(n) kost.

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))  # 6

Randgevallen in histogramproblemen

Belangrijke randgevallen:

  • Overal dezelfde hoogte: de volledige array vormt één rechthoek; antwoord = n × hoogte
  • Monotoon oplopend: er wordt pas bij de wachtwaarde een element van de stapel gehaald; het oppervlak van de laatste staaf is maximaal
  • Eén staaf: antwoord = height[0]
  • Staven met hoogte 0: ze werken als natuurlijke wachtwaarden en splitsen het histogram op in onafhankelijke delen

De wachtwaarde (door 0 toe te voegen) aan het einde handelt het monotoon oplopende geval af door alle overgebleven staven aan het einde van de stapel te verwijderen. Zonder die waarde heb je na de hoofditeratie een afzonderlijke opschoningslus nodig.

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)

Alternatief: verdeel en heers

Het histogramprobleem kan ook worden opgelost met verdeel en heers: splits bij de staaf met de minimale hoogte, los elke helft recursief op en vergelijk die resultaten met de rechthoek die de volledige breedte omvat en de minimale hoogte heeft. Dit geeft gemiddeld O(n log n), maar in het slechtste geval O(n²) voor gesorteerde invoer.

De aanpak met een monotone stapel is met O(n) in het slechtste geval strikt beter. Toch verdiept inzicht in de aanpak van verdelen en heersen je intuïtie bij problemen en verklaart het waarom de staaf met de minimale hoogte in elk segment altijd de beperkende factor is voor rechthoeken over de volledige breedte.

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]))  # 10

Histogrampatroon: aantal deelarrays

Een verwant probleem met dezelfde stapeltechniek: tel het aantal deelarrays in een histogram waarvan het minimale element gelijk is aan een bepaald doel. Dit beantwoord je door voor elke staaf het PSE en NSE te berekenen en vervolgens de formule (i - pse[i]) × (nse[i] - i) te gebruiken. Die telt de subhistogrammen waarin staaf i het minimum is.

Deze techniek van 'aantal links × aantal rechts' komt voor in verschillende LeetCode-problemen: de som van minima van deelarrays (907), het aantal deelstrings met uitsluitend unieke tekens en problemen met de bijdrage-techniek. De monotone stapel berekent PSE en NSE in O(n), waardoor een bijdrage per element in O(1) mogelijk wordt.

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]))  # 444

Praktische tips voor sollicitatiegesprekken

Als je tijdens een sollicitatiegesprek een histogramprobleem ziet, volg dan deze controlelijst:

  1. Verduidelijk: kunnen hoogtes 0 zijn? Wat is de uitvoer — oppervlakte, indexen of aantal?
  2. Begin met een brute-forceaanpak en vermeld een complexiteit van O(n²) of O(n³)
  3. Vermeld dat de bijdrage van elke staaf afhangt van het bereik links en rechts tot aan de dichtstbijzijnde kortere staaf
  4. Introduceer PSE/NSE → monotone stapel → oplossing in O(n)
  5. Gebruik de sentineltruc (voeg 0 toe) om de code eenvoudiger te maken
  6. Werk een klein voorbeeld uit op het whiteboard

Veelvoorkomende vervolgvraag: breid dit uit naar twee dimensies (maximale rechthoek). Laat zien dat je dit kunt terugbrengen tot n histogramproblemen, elk in O(n), voor een totaal van 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})')

Som van bereiken van deelarrays en vergelijkbare varianten

De PSE/NSE-techniek generaliseert naar verschillende LeetCode-problemen. Som van bereiken van deelarrays (2104) vraagt om de som van (max - min) over alle deelarrays. Dit is gelijk aan (som van maxima van deelarrays) minus (som van minima van deelarrays), die elk met een monotone stapel in O(n) worden berekend. Aantal zichtbare mensen in een wachtrij (1944) gebruikt een afnemende stapel, waarbij elke verwijdering een zichtbaar persoon telt. Je herkent deze familie van problemen aan de formulering 'hoe ver kan elk element domineren?' — het antwoord is altijd PSE/NSE met een monotone stapel.

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]))  # 59

Korte controle

Controleer je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep in deze les.

Beantwoord dit in de interactieve les

Samenvatting van de les

In deze les heb je geleerd: voor elke staaf worden de grenzen van de grootste rechthoek die de staaf bevat bepaald door de dichtstbijzijnde kortere staaf aan elke kant (PSE en NSE), een oplopende monotone stapel berekent alle PSE/NSE-grenzen in één doorgang in O(n) door beide grenzen te vinden wanneer staven worden verwijderd, en door een sentinel 0 toe te voegen worden alle staven van de stapel verwijderd, waardoor de code wordt vereenvoudigd tot één lus. Hierna gebruiken we de monotone dubbelzijdige wachtrij om het maximum in een schuivend venster in O(n) te vinden.

Gratis beginnen

Leer Python met een AI-tutor — gratis

Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.

Cursussen
30
Lessen
120
Gratis beginnen met lerenBekijk de volledige cursus

Veelgestelde vragen

Is de les “Grootste rechthoek in een histogram” gratis?

Ja — je kunt hier op het web alle 3 lessen van het leerpad DSA Interview Prep, waaronder “Grootste rechthoek in een histogram”, gratis volledig lezen. Daarna ontgrendelt CoddyKit PRO alle lessen, plus interactieve oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. De cursus DSA Interview Prep bevat in totaal 4 lessen.

Wat leer ik in “Grootste rechthoek in een histogram”?

Gebruik een monotone stack om linkergrenzen bij te houden en bereken in één doorgang de rechthoek met de grootste oppervlakte die in een histogram past. Je oefent met DSA Interview Prep door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.

Heb ik ervaring nodig om met DSA Interview Prep te beginnen?

Ervaring vooraf is niet nodig. DSA Interview Prep op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 2 van 4.

Hoe lang duurt de les “Grootste rechthoek in een histogram”?

De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.

Kan ik code schrijven en uitvoeren in deze les over DSA Interview Prep?

Ja. Elke les over DSA Interview Prep bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.

Alle lessen in deze cursus

  1. Monotone stack: oplopend versus aflopend
  2. Grootste rechthoek in een histogram
  3. Maximum in een sliding window met een monotone deque
  4. Trapping Rain Water: stack en two-pointer
← Terug naar DSA Interview Prep