DSA Interview Prep · leksjon

Største rektangel i et histogram

Bruk en monoton stakk til å holde oversikt over venstre grenser og beregne det største rektangelarealet som får plass i et histogram, i én gjennomgang.

Leksjon 2 av 413 trinn

Største rektangel i et histogram er en gratis leksjon i DSA Interview Prep på CoddyKit. Dette er leksjon 2 av 4. Du kan lese valgfritt 3 leksjoner fra denne læringsstien gratis i sin helhet – deretter låser CoddyKit PRO opp alle leksjoner, samt praktisk øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i DSA Interview Prep, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.

Problem: største rektangel i et histogram

Problemet Largest Rectangle in Histogram (LeetCode 84) gir en array med ikke-negative heltall som representerer høyden på søyler i et histogram, der hver søyle har bredde 1. Finn arealet til det største rektangelet som kan dannes i histogrammet. Rektangelet må omfatte sammenhengende søyler, og høyden begrenses av den laveste søylen det dekker.

En brute-force-tilnærming: For hvert par (i, j) beregner De minimumshøyden i [i, j] og multipliserer den med (j - i + 1). Dette gir O(n³), eller O(n²) med forhåndsberegnede minimumsverdier — det er for tregt. Løsningen med monoton stakk kjø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))  # 10

Nøkkelinnsikt: Hva begrenser rektangelet til hver søyle

For hver søyle i med høyde h strekker det største rektangelet der søylen kan være minimumshøyden seg mot venstre til den første søylen som er lavere enn h, og mot høyre til den første søylen som er lavere enn h. Bredden er right_boundary - left_boundary - 1, og arealet er h × width.

Dette omformulerer problemet: For hver søyle finner vi dens forrige mindre element (PSE) og neste mindre element (NSE). Dette er nøyaktig det en monoton økende stakk beregner. I det øyeblikket vi tar søyle i av stakken (fordi en lavere søyle er funnet), er den nåværende søylen dens NSE, og toppen av stakken etter avtakningen 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 i én gjennomgang med monoton stakk

Tilnærmingen med to gjennomganger ovenfor fungerer, men kan slås sammen til én gjennomgang. Behandle søylene fra venstre mot høyre med en monoton økende stakk. Når søyle i er lavere enn toppen av stakken, tar De toppen av stakken av — høyden til søylen som tas av, er høyden til et rektangel, den høyre grensen er i, og den venstre grensen er den nye toppen av stakken + 1.

Et vanlig triks er å legge til en vaktverdi på 0 på slutten av heights. Dette sørger for at alle søylene tas av stakken til slutt, selv om ingen lavere søyle dukker opp naturlig. Uten vaktverdien må De rydde opp i de gjenværende elementene etter løkken.

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

Gjennomgang av én-pass-algoritmen

La oss gå gjennom [2, 1, 5, 6, 2, 3, 0] (med vaktverdi) trinn for trinn:

i=0, h=2: legg 0 på stakken. Stakk: [0]
i=1, h=1: ta 0 av stakken (h=2, width=1, area=2). Stakken er tom, legg 1 på stakken. Stakk: [1]
i=2, h=5: 5>1, legg 2 på stakken. Stakk: [1,2]
i=3, h=6: 6>5, legg 3 på stakken. Stakk: [1,2,3]
i=4, h=2: ta 3 av stakken (h=6,width=4-2-1=1,area=6), ta 2 av stakken (h=5,width=4-1-1=2,area=10★), 2>1, stopp. Legg 4 på stakken. Stakk: [1,4]
i=5, h=3: 3>2, legg 5 på stakken. Stakk: [1,4,5]
i=6, vaktverdi h=0: ta alle av stakken og beregn arealene …

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 av bredden: Hvorfor i - stack[-1] - 1?

Når vi tar søyle j av stakken, vet vi at den høyre grensen for rektangelet til j er i (den første søylen til høyre som er lavere enn j). Den venstre grensen er søylen som ligger rett under j i stakken etter avtakningen — kall den k. Bredden blir derfor i - k - 1 (søylene fra k+1 til og med i-1).

Hvis stakken er tom etter avtakningen, strekker rektangelet til j seg helt til venstrekanten (indeks 0). Bredden er ganske enkelt i (indeksene 0 til i-1, som alle er minst like høye som heights[j]). Dette er spesialtilfellet 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 matrise

Maximal Rectangle (LeetCode 85) utvider histogramproblemet til en todimensjonal binær matrise. For hver rad beregner De høyden av sammenhengende 1-ere over hver celle. Dette danner et histogram for raden. Bruk algoritmen for største rektangel i et histogram på histogrammet for hver rad. Det største resultatet på tvers av alle radene er svaret.

Dette reduserer et todimensjonalt problem til m gjentatte endimensjonale histogramproblemer. Tidskompleksiteten er O(m × n) for en matrise med m rader og n kolonner — én histogramgjennomgang per rad, der hver gjennomgang 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))  # 6

Spesialtilfeller i histogramproblemer

Viktige spesialtilfeller som må håndteres:

Samme høyde overalt: hele arrayen danner ett rektangel; svaret er n × høyde
Monotont økende: ingen søyle tas av før vaktverdien; den siste søylens areal er maksimum
Én søyle: svaret er height[0]
Søyler med høyde 0: De fungerer som naturlige vaktverdier og deler histogrammet i uavhengige segmenter

Vaktverdien (ved å legge til 0) på slutten håndterer det monotont økende tilfellet ved å tvinge alle gjenværende søyler av stakken til slutt. Uten den trenger De en separat oppryddingsløkke etter hovedgjennomgangen.

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 opp ved søylen med minimumshøyden, løs hvert halvsegment rekursivt, og sammenlign med rektangelet som dekker hele bredden med minimumshøyden. Dette gir O(n log n) i gjennomsnitt, men O(n²) i verste fall for sorterte inndata.

Tilnærmingen med monoton stakk er entydig bedre, med O(n) i verste fall. Det gir likevel bedre intuisjon for problemet å forstå del-og-hersk-tilnærmingen, og det forklarer hvorfor søylen med minimumshøyden i ethvert segment alltid er den begrensende faktoren for rektangler som dekker hele bredden.

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

Histogrammønster: antall delarrayer

Et beslektet problem som bruker samme stakkteknikk: Tell antallet delarrayer i et histogram der minimumselementet er lik et bestemt mål. Dette løses ved å beregne PSE og NSE for hver søyle og deretter bruke formelen (i - pse[i]) × (nse[i] - i), som teller delhistogrammene der søyle i er minimumselementet.

Denne teknikken med «antall til venstre × antall til høyre» dukker opp i flere LeetCode-problemer: sum av minimumsverdier i delarrayer (907), antall delstrenger med bare unike tegn og problemer som bruker bidragsteknikken. Den monotone stakken beregner PSE og NSE i O(n), slik at bidraget for hvert element 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]))  # 444

Praktiske tips til jobbintervju

Når De får en histogramoppgave i et jobbintervju, kan De følge denne sjekklisten:

Avklar: Kan høyder være 0? Hva er resultatet – areal, indekser eller antall?
Start med brute force, og oppgi kompleksiteten O(n²) eller O(n³)
Nevn at hvert stakks bidrag avhenger av utstrekningen mot venstre og høyre frem til nærmeste kortere stakk
Introduser PSE/NSE → monoton stakk → løsning i O(n)
Bruk sentinel-trikset (legg til 0) for å forenkle koden
Gå gjennom et lite eksempel på tavlen

Et vanlig oppfølgingsspørsmål er å utvide løsningen til 2D (maksimalt rektangel). Vis at problemet kan reduseres til n histogramoppgaver, hver i O(n), slik at total kompleksitet blir 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})')

Summen av delarrayintervaller og lignende varianter

PSE/NSE-teknikken kan generaliseres til flere LeetCode-oppgaver. Sum of Subarray Ranges (2104) ber om summen av (maksimum − minimum) over alle delarrayer. Dette er lik (summen av maksimumsverdiene i delarrayene) minus (summen av minimumsverdiene i delarrayene), der begge delene beregnes med en monoton stakk i O(n). Number of Visible People in a Queue (1944) bruker en avtakende stakk der hver fjerning teller én synlig person. At De kjenner igjen denne problemfamilien, kommer av at De legger merke til formuleringen «for hvert element, hvor langt kan det dominere?» – svaret er alltid PSE/NSE med en monoton stakk.

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

Rask sjekk

Test forståelsen Deres av konseptene i Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.

Besvar den i den interaktive leksjonen

Oppsummering av leksjonen

I denne leksjonen lærte De: for hver stakk bestemmes grensene for det største rektangelet som inneholder stakken, av den nærmeste kortere stakken på hver side (PSE og NSE), en monoton stigende stakk beregner alle PSE/NSE-grensene i én gjennomgang i O(n) ved å finne begge når stakker fjernes, og ved å legge til en sentinel 0 sørger De for at alle stakker fjernes fra stakken, slik at koden forenkles til én løkke. Deretter skal vi bruke en monoton deque til å finne maksimum i glidende vinduer i O(n).

Gratis å komme i gang

Lær deg Python med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 30
Leksjoner: 120

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Største rektangel i et histogram» gratis?

Ja – du kan lese valgfritt 3 av leksjonene i læringsstien DSA Interview Prep, inkludert «Største rektangel i et histogram», gratis i sin helhet her på nettet. Deretter låser CoddyKit PRO opp alle leksjoner, samt interaktiv øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.

Hva lærer jeg i «Største rektangel i et histogram»?

Bruk en monoton stakk til å holde oversikt over venstre grenser og beregne det største rektangelarealet som får plass i et histogram, i én gjennomgang. Du øver på DSA Interview Prep med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med DSA Interview Prep?

Ingen tidligere erfaring er nødvendig. DSA Interview Prep på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.

Hvor lang tid tar leksjonen «Største rektangel i et histogram»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne DSA Interview Prep-leksjonen?

Ja. Alle DSA Interview Prep-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

← Tilbake til DSA Interview Prep