Monotonisen pinon malli
Soveltakaa monotonista pinoa daily-temperatures-, largest-rectangle-in-histogram- ja next-greater-element-tehtäviin ajassa O(n).
Monotonisen pinon malli on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 3/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.
Mikä on monotoninen pino
Monotoninen pino on pino, joka ylläpitää alkioidensa järjestystä koskevaa invarianttia. Kasvavassa monotonisessa pinossa alkiot kasvavat alhaalta ylöspäin, kun taas laskevassa monotonisessa pinossa alkiot pienenevät alhaalta ylöspäin. Kun uusi alkio rikkoo invariantin, alkioita poistetaan pinosta, kunnes invariantti on jälleen voimassa, minkä jälkeen uusi alkio lisätään pinoon.
Tämän yksinkertaisen mekanismin avulla kyselyihin, joissa etsitään 'lähintä suurempaa alkiota' tai 'lähintä pienempää alkiota', voidaan vastata ajassa O(n), vaikka suoraviivainen ratkaisu vaatisi sisäkkäisiä O(n²)-silmukoita.
# Build a monotonically increasing stack from [3,1,2,5,4]
nums = [3, 1, 2, 5, 4]
stack = []
for n in nums:
while stack and stack[-1] > n:
stack.pop() # remove elements that violate increasing order
stack.append(n)
print('stack:', stack)Seuraava suurempi alkio (LeetCode 496)
Etsikää kullekin alkiolle ensimmäinen sen oikealla puolella oleva aidosti suurempi alkio. Raakavoimainen O(n²)-ratkaisu käy jokaisesta kohdasta alkiot läpi oikealle. Monotonista pinoa käyttävä ratkaisu ylläpitää laskevaa indeksipinoa. Kun vastaan tulee suurempi alkio, poistetaan kaikki pienempiä alkioita vastaavat indeksit — niiden 'seuraava suurempi alkio' on nykyinen alkio. Pinoon jäljelle jääneillä indekseillä ei ole seuraavaa suurempaa alkiota, joten niiden vastaukseksi tulee -1.
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, decreasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
j = stack.pop()
result[j] = val
stack.append(i)
return result
print(nextGreaterElement([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
print(nextGreaterElement([1, 3, 2, 4])) # [3, 4, 4, -1]Seuraava suurempi alkio kehätaulukossa
LeetCode 503:n Word Ladder -ongelmassa on sama tehtävä, mutta taulukkoa käsitellään kehämäisenä. Kun loppuun on päästy, palataan alkuun ja jatketaan tarkistamista. Vinkki: käykää taulukko läpi kahdesti eli indekseillä 0–2n-1 ja käyttäkää i % n -lauseketta alkuperäisen taulukon indeksointiin. Lisätkää pinoon vain indeksit väliltä [0, n-1], jotta samaa käsittelyä ei tehdä kahdesti.
def nextGreaterElements(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
j = stack.pop()
result[j] = nums[i % n]
if i < n:
stack.append(i)
return result
print(nextGreaterElements([1, 2, 1])) # [2, -1, 2]
print(nextGreaterElements([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]Päivittäiset lämpötilat: täydellinen ratkaisu
LeetCode 739 uudelleen tarkasteltuna: kuinka monta päivää kuluu kustakin päivästä lämpimämpään päivään? Monotoninen pino sisältää niiden päivien indeksit, joiden lämpötilat ovat laskevassa järjestyksessä. Kun löydetään lämpimämpi päivä i, pinosta poistetaan kaikki viileämpien päivien indeksit j ja asetetaan result[j] = i - j. Pinoon jäljelle jääneille päiville ei löytynyt lämpimämpää päivää, joten niiden tulokseksi jää 0.
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices, decreasing temperatures
for i, t in enumerate(temperatures):
while stack and temperatures[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(dailyTemperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]Edellinen pienempi alkio
'Edellinen pienempi alkio' -kyselyssä etsitään kullekin alkiolle lähin sitä vasemmalla oleva pienempi arvo. Käyttäkää vasemmalta oikealle käsiteltävää kasvavaa monotonista pinoa. Ennen indeksin i lisäämistä pinoon pinon päällimmäinen alkio on edellinen pienempi alkio, koska kaikki alkion nums[i] suuremmat alkiot on jo poistettu aiempien lisäysten yhteydessä.
def previousSmallerElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, increasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] >= val:
stack.pop()
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
print(previousSmallerElement([4, 5, 2, 10, 8])) # [-1, 4, -1, 2, 2]
print(previousSmallerElement([3, 1, 2])) # [-1, -1, 1]Histogrammin suurin suorakulmio
LeetCode 84:n Largest Rectangle in Histogram -ongelmassa käytetään monotonista kasvavaa indeksipinoa. Poistakaa kunkin palkin kohdalla kaikki nykyistä palkkia korkeammat palkit. Jokaiselle poistetulle palkille h sen oikea raja on nykyinen indeksi i ja vasen raja uuden pinon päällimmäinen indeksi + 1 (tai 0, jos pino on tyhjä). Pinta-ala = h × (right - left). Lisätkää loppuun korkeudeltaan 0 oleva vartioalkio, jotta kaikki jäljelle jäävät palkit poistetaan lopuksi.
def largestRectangleArea(heights):
heights = heights + [0] # sentinel
stack = [] # indices, increasing heights
result = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0
width = i - left
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2, 1, 5, 6, 2, 3])) # 10
print(largestRectangleArea([2, 4])) # 4
print(largestRectangleArea([1])) # 1Maksimaalinen suorakulmio (LeetCode 85)
LeetCode 85:n 'Maximal Rectangle' laajentaa histogrammiongelman kaksiulotteiseen binäärimatriisiin. Laskekaa kullakin rivillä kertyneet palkkikorkeudet: jos matrix[row][col] == '1', korkeus on tämän solun ja sen yläpuolella olevien peräkkäisten ykkösten määrä. Soveltakaa sitten kunkin rivin korkeusjoukkoon histogrammin suurimman suorakulmion algoritmia. Aikavaativuus on O(m × n) m×n-matriisille.
def maximalRectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
result = 0
def largest_in_hist(h):
h = h + [0]
stack, best = [], 0
for i, val in enumerate(h):
while stack and h[stack[-1]] > val:
height = h[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
for row in matrix:
for j, cell in enumerate(row):
heights[j] = heights[j] + 1 if cell == '1' else 0
result = max(result, largest_in_hist(heights[:]))
return result
m = [['1','0','1','0','0'],['1','0','1','1','1'],
['1','1','1','1','1'],['1','0','0','1','0']]
print(maximalRectangle(m)) # 6Sadeveden kerääntyminen: pinoon perustuva ratkaisu
LeetCode 42:n 'Trapping Rain Water' -ongelmassa käytetään pinoa: ylläpidetään laskevaa indeksipinoa. Kun vastaan tulee korkeampi palkki, muodostuu kuoppa. Poistakaa kuopan pohja, laskekaa veden leveydeksi (current_index - stack_top - 1) ja korkeudeksi (min(current_bar, new_stack_top_bar) - valley_height). Summatkaa kaikki osuudet. Aikavaativuus: O(n), tilavaativuus: O(n).
def trap(height):
stack = []
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = stack.pop()
if not stack:
break
left = stack[-1]
width = i - left - 1
bounded_h = min(h, height[left]) - height[bottom]
water += width * bounded_h
stack.append(i)
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap([4,2,0,3,2,5])) # 9Monotonisen pinon ongelmien tunnistaminen
Monotoninen pino on oikea työkalu, jos ongelmassa etsitään seuraavaa tai edellistä suurempaa tai pienempää alkiota, kunkin alkion vastaus riippuu tietyn suunnan alkioista tai suoraviivainen O(n²)-ratkaisu kävisi jokaisesta alkiosta vasemmalle tai oikealle. Pino sisältää ehdokkaat, jotka voivat olla tulevien alkioiden vastauksia, ja hylkää ne heti, kun parempi ehdokas saapuu.
Päättäkää aina etukäteen, käytättekö kasvavaa pinoa (seuraavan tai edellisen pienemmän alkion etsimiseen) vai laskevaa pinoa (seuraavan tai edellisen suuremman alkion etsimiseen) ja mistä suunnasta käsittelette alkiot.
Amortisoidun O(n)-ajan analyysi
Monotoniset pinoalgoritmit voivat aluksi näyttää O(n log n)- tai O(n²)-aikaisilta, koska for-silmukan sisällä on while-silmukka. Jokainen alkio kuitenkin lisätään pinoon enintään kerran ja poistetaan pinosta enintään kerran. Lisäysoperaatioita on yhteensä n ja poisto-operaatioita enintään n. Kaikkien iteraatioiden yhteenlaskettu työmäärä on siis 2n operaatiota — amortisoitu aikavaativuus on O(n), ei O(n²).
# Count total pushes and pops for n=1000
n = 1000
nums = list(range(n, 0, -1)) # worst case for decreasing stack
stack = []
pushes = pops = 0
for val in nums:
while stack and stack[-1] < val:
stack.pop()
pops += 1
stack.append(val)
pushes += 1
print(f'n={n}, pushes={pushes}, pops={pops}, total={pushes+pops}')
# Total <= 2*nYhteenveto: monotonisen pinon invariantin valinta
Valitkaa pinon suunta kyselyn perusteella. Käyttäkää seuraavan suuremman alkion etsimiseen laskevaa pinoa — poistakaa alkioita, kun nykyinen alkio on suurempi. Käyttäkää seuraavan pienemmän alkion etsimiseen kasvavaa pinoa — poistakaa alkioita, kun nykyinen alkio on pienempi. Käyttäkää suurimman suorakulmion etsimiseen kasvavaa pinoa ja poistakaa alkioita, kun lyhyempi palkki tulee vastaan. Käyttäkää liukuvan ikkunan maksimiin laskevaa dequeta ja poistakaa alkioita molemmista päistä.
Kun kirjoitatte invariantin kommentiksi ennen koodaamista, logiikka selkeytyy ja virheenkorjaus nopeutuu.
Pikatesti
Testatkaa tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -aiheen käsitteiden ymmärtämistä.
Oppitunnin yhteenveto
Tässä oppitunnissa opitte, että monotoninen pino ylläpitää järjestysinvarianttia poistamalla sitä rikkovat alkiot ennen uuden alkion lisäämistä, laskevat pinot vastaavat seuraavaa suurempaa alkiota koskeviin kyselyihin ja kasvavat pinot seuraavaa pienempää alkiota koskeviin kyselyihin ja kokonaisaikavaativuus on amortisoitu O(n), koska jokainen alkio lisätään pinoon ja poistetaan pinosta enintään kerran. Seuraavaksi toteutamme jonoja pinojen avulla ja pinoja jonojen avulla.
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 ”Monotonisen pinon malli” ilmainen?
Kyllä – oppitunnin ”Monotonisen pinon malli” 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 ”Monotonisen pinon malli”?
Soveltakaa monotonista pinoa daily-temperatures-, largest-rectangle-in-histogram- ja next-greater-element-tehtäviin ajassa O(n). 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 3/4.
Kuinka kauan ”Monotonisen pinon malli”-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
- Pinon toteutus ja sovellukset
- Jonon toteutus ja deque
- Monotonisen pinon malli
- Pinon ja jonon vastavuoroinen simulointi