Histogrammin suurin suorakulmio
Käyttäkää monotonista pinoa vasemmanpuoleisten rajojen seuraamiseen ja laskekaa histogrammiin sopivan suurimman suorakulmion pinta-ala yhdellä läpikäynnillä.
Histogrammin suurin suorakulmio on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 2/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Ongelma: histogrammin suurin suorakulmio
Histogrammin suurimman suorakulmion ongelmassa (LeetCode 84) annetaan ei-negatiivisia kokonaislukuja sisältävä taulukko, joka esittää histogrammin pylväiden korkeuksia. Jokaisen pylvään leveys on 1. Etsikää histogrammista muodostettavissa olevan suurimman suorakulmion pinta-ala. Suorakulmion on katettava vierekkäisiä pylväitä, ja sen korkeuden määrää sen kattamista pylväistä lyhin.
Brute-force-lähestymistavassa lasketaan jokaiselle parille (i, j) välin [i, j] pienin korkeus ja kerrotaan se luvulla (j - i + 1). Tämä on O(n³) tai esilaskettujen minimien avulla O(n²) — liian hidasta. Monotoniseen pinoon perustuva ratkaisu toimii O(n)-ajassa.
# 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)) # 10Keskeinen oivallus: mikä rajoittaa kunkin pylvään suorakulmiota?
Jos pylvään i korkeus on h, suurin suorakulmio, jossa se voi olla pienin pylväs, ulottuu vasemmalle ensimmäiseen h:ta matalampaan pylvääseen asti ja oikealle ensimmäiseen h:ta matalampaan pylvääseen asti. Leveys on right_boundary - left_boundary - 1 ja pinta-ala on h × width.
Tämä muotoilee ongelman uudelleen: jokaiselle pylväälle etsitään sen edellinen pienempi alkio (PSE) ja seuraava pienempi alkio (NSE). Monotonisesti kasvava pino laskee juuri nämä arvot. Kun pylväs i poistetaan pinosta (koska lyhyempi pylväs on löytynyt), nykyinen pylväs on sen NSE ja pinon huippu poistamisen jälkeen on sen 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)Yhden läpikäynnin ratkaisu monotonisella pinolla
Edellä kuvattu kahden läpikäynnin ratkaisu toimii, mutta läpikäynnit voidaan yhdistää yhdeksi. Käsitellään pylväät vasemmalta oikealle monotonisesti kasvavalla pinolla. Kun pylväs i on pinon huippua matalampi, poistetaan pinon huippu — poistettavan pylvään korkeus on suorakulmion korkeus, sen oikea raja on i ja vasen raja on uuden pinon huipun arvo + 1.
Vakiotemppu on lisätä korkeuksien loppuun sentinelli 0. Näin kaikki pylväät poistetaan pinosta lopuksi, vaikka luonnollista lyhyempää pylvästä ei myöhemmin tulisikaan vastaan. Ilman sentinelliä jäljelle jääville pinon alkioille tarvitaan pääsilmukan jälkeinen erillinen siivousvaihe.
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])) # 16Yhden läpikäynnin algoritmin vaiheittainen läpikäynti
Käydään [2, 1, 5, 6, 2, 3, 0] (sentinelli mukaan lukien) vaihe vaiheelta läpi:
- i=0, h=2: lisätään 0 pinoon. Pino: [0]
- i=1, h=1: poistetaan 0 pinosta (h=2, width=1, area=2). Pino on tyhjä, lisätään 1 pinoon. Pino: [1]
- i=2, h=5: 5>1, lisätään 2 pinoon. Pino: [1,2]
- i=3, h=6: 6>5, lisätään 3 pinoon. Pino: [1,2,3]
- i=4, h=2: poistetaan 3 pinosta (h=6,width=4-2-1=1,area=6), poistetaan 2 pinosta (h=5,width=4-1-1=2,area=10★), 2>1, lopetetaan. Lisätään 4 pinoon. Pino: [1,4]
- i=5, h=3: 3>2, lisätään 5 pinoon. Pino: [1,4,5]
- i=6, sentinelli h=0: poistetaan kaikki alkiot pinosta ja lasketaan pinta-alat...
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])Leveyden laskeminen: miksi i - stack[-1] - 1?
Kun pylväs j poistetaan pinosta, tiedämme, että j:n suorakulmion oikea raja on i (ensimmäinen j:tä oikealla oleva lyhyempi pylväs). Vasen raja on pylvään j alapuolella pinossa poistamisen jälkeen oleva pylväs — kutsutaan sitä k:ksi. Leveys on siis i - k - 1 (pylväät k+1:stä i-1:een, päätepisteet mukaan lukien).
Jos pino on poistamisen jälkeen tyhjä, j:n suorakulmio ulottuu kokonaan vasempaan reunaan asti (indeksiin 0). Leveys on tällöin yksinkertaisesti i (indeksit 0–i-1, jotka kaikki ovat vähintään yhtä korkeita kuin heights[j]). Tämä on erikoistapaus 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])Suurin suorakulmio binäärimatriisissa
Suurin suorakulmio (LeetCode 85) laajentaa histogrammiongelman kaksiulotteiseen binäärimatriisiin. Kullakin rivillä lasketaan kunkin solun yläpuolella peräkkäin olevien ykkösten määrä. Näin muodostuu kyseistä riviä vastaava histogrammi. Suurimman histogrammisuorakulmion algoritmia sovelletaan jokaisen rivin histogrammiin. Kaikkien rivien suurin tulos on vastaus.
Kaksiulotteinen ongelma supistuu n:ksi peräkkäiseksi yksiulotteiseksi histogrammiongelmaksi. Aikavaativuus on O(m × n), kun matriisissa on m riviä ja n saraketta: jokaisella rivillä tehdään yksi histogrammin läpikäynti, joka vie O(n)-ajan.
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)) # 6Histogrammiongelmien reunatapaukset
Tärkeitä käsiteltäviä reunatapauksia:
- Kaikki saman korkuisia: koko taulukko muodostaa yhden suorakulmion; answer = n × height
- Monotonisesti kasvava: yhtään poistoa ei tapahdu ennen sentinelliä; viimeisen pylvään pinta-ala on suurin
- Yksi pylväs: answer = height[0]
- Korkeudeltaan 0 olevat pylväät: ne toimivat luonnollisina sentinelleinä ja jakavat histogrammin toisistaan riippumattomiin osiin
Loppuun lisättävä sentinelli (0) käsittelee monotonisesti kasvavan tapauksen pakottamalla kaikki jäljellä olevat pylväät poistettaviksi. Ilman sitä pääsilmukan jälkeen tarvitaan erillinen siivoussilmukka.
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)Hajota ja hallitse -vaihtoehto
Histogrammiongelma voidaan ratkaista myös hajota ja hallitse -menetelmällä: jaetaan ongelma pienimmän korkuisen pylvään kohdalta, ratkaistaan kumpikin puolikas rekursiivisesti ja verrataan tulosta koko leveyden kattavaan suorakulmioon, jonka korkeutena on pienin korkeus. Keskimääräinen aikavaativuus on O(n log n), mutta järjestetyillä syötteillä pahimman tapauksen aikavaativuus on O(n²).
Monotoniseen pinoon perustuva ratkaisu on pahimmassakin tapauksessa parempi, sillä sen aikavaativuus on O(n). Hajota ja hallitse -menetelmän ymmärtäminen syventää kuitenkin ongelman hahmottamista ja selittää, miksi segmentin pienimmän korkeuden pylväs rajoittaa aina koko leveyden kattavia suorakulmioita.
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])) # 10Histogrammikaava: osataulukoiden määrä
Samaan pinoon perustuvaan tekniikkaan liittyvä ongelma on laskea histogrammin osataulukot, joissa pienin alkio on jokin tietty kohdearvo. Tämä ratkaistaan laskemalla kullekin pylväälle PSE ja NSE ja käyttämällä kaavaa (i - pse[i]) × (nse[i] - i), joka laskee niiden alihistogrammien määrän, joissa pylväs i on pienin.
Tämä ”vasen määrä × oikea määrä” -tekniikka esiintyy useissa LeetCode-ongelmissa: osataulukoiden minimien summa (907), sellaisten osamerkkijonojen määrä, joissa kaikki merkit ovat yksikäsitteisiä, sekä kontribuutiotekniikkaa käyttävät ongelmat. Monotoninen pino laskee PSE:n ja NSE:n O(n)-ajassa, mikä mahdollistaa O(1)-käsittelyn kunkin alkion kontribuutiolle.
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])) # 444Käytännön vinkkejä työhaastatteluun
Kun haastattelussa tulee vastaan histogrammiongelma, käykää tämä tarkistuslista läpi:
- Täsmennetään: voivatko korkeudet olla 0? Mitä tulostetaan — pinta-ala, indeksit vai lukumäärä?
- Aloitetaan brute force -ratkaisusta ja ilmoitetaan aikavaativuudeksi O(n²) tai O(n³)
- Mainitaan, että kunkin palkin vaikutus määräytyy sen vasemman ja oikean puoleisen ulottuvuuden perusteella lähimpään lyhyempään palkkiin asti
- Esitellään PSE/NSE → monotoninen pino → O(n)-ratkaisu
- Käsitellään sentinel-temppu (lisätään loppuun 0), jotta koodi yksinkertaistuu
- Jäljitetään pieni esimerkki taululle
Yleinen jatkokysymys on laajentaminen 2D:hen (suurin suorakulmio). Osoittakaa, että ongelma voidaan pelkistää n:ksi histogrammiongelmaksi, joista jokainen ratkaistaan ajassa O(n), jolloin kokonaisvaativuudeksi saadaan 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})')Osataulukoiden vaihteluvälien summa ja vastaavat muunnelmat
PSE/NSE-tekniikka yleistyy useisiin LeetCode-tehtäviin. Osataulukoiden vaihteluvälien summa (2104) pyytää laskemaan kaikkien osataulukoiden (max - min) -arvojen summan. Tämä on yhtä suuri kuin osataulukoiden maksimiarvojen summasta vähennettynä osataulukoiden minimiarvojen summa; molemmat voidaan laskea monotonisella pinolla ajassa O(n). Jonossa näkyvien henkilöiden määrä (1944) käyttää vähenevää pinoa, jossa jokainen poisto laskee yhden näkyvän henkilön. Tämän ongelmaperheen tunnistaa siitä, että huomaa ilmauksen ”kuinka pitkälle kukin alkio voi hallita?” — vastaus on aina PSE/NSE monotonisen pinon avulla.
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])) # 59Pikatarkistus
Testatkaa tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -aiheiden ymmärtämistä.
Oppitunnin kertaus
Tässä oppitunnissa opitte, että kunkin palkin suurimman siihen sisältyvän suorakulmion rajat määräytyvät kummallakin puolella olevan lähimmän lyhyemmän palkin perusteella (PSE ja NSE), monotonisesti kasvava pino laskee kaikki PSE/NSE-rajat yhdellä O(n)-läpikäynnillä, kun molemmat rajat löydetään palkkeja poistettaessa ja sentinel-arvon 0 lisääminen varmistaa, että kaikki palkit poistetaan pinosta, jolloin koodi voidaan yksinkertaistaa yhdeksi silmukaksi. Seuraavaksi ratkaistaan liukuvan ikkunan maksimiarvo monotonisen dequen avulla ajassa O(n).
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Histogrammin suurin suorakulmio” ilmainen?
Kyllä – oppitunnin ”Histogrammin suurin suorakulmio” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Histogrammin suurin suorakulmio”?
Käyttäkää monotonista pinoa vasemmanpuoleisten rajojen seuraamiseen ja laskekaa histogrammiin sopivan suurimman suorakulmion pinta-ala yhdellä läpikäynnillä. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 2/4.
Kuinka kauan ”Histogrammin suurin suorakulmio”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Monotoninen pino: kasvava ja vähenevä
- Histogrammin suurin suorakulmio
- Liukuikkunan maksimi monotonisella dequella
- Trapping Rain Water: pino ja kaksi osoitinta