Monotoninen pino: kasvava ja vähenevä
Ylläpitäkää kasvavaa tai vähenevää pinoa, jotta voitte vastata seuraavaa suurempaa ja edellistä pienempää alkiota koskeviin kyselyihin tehokkaasti ajassa O(n).
Monotoninen pino: kasvava ja vähenevä on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 1/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 pitää alkionsa järjestyksessä: ne ovat joko aina kasvavassa järjestyksessä pohjalta huipulle tai aina laskevassa järjestyksessä. Ennen uuden alkion lisäämistä pinoon poistetaan kaikki alkiot, jotka rikkovat monotonista invarianttia. Tämän rajoitetun rakenteen avulla voidaan ratkaista O(n):ssä ongelmia, jotka vaatisivat muuten O(n²):n sisäkkäisiä silmukoita.
Keskeinen havainto on, että kukin alkio lisätään pinoon ja poistetaan siitä enintään kerran. Siksi koko taulukon läpikäynnin aikana suoritettavien operaatioiden kokonaismäärä on O(n), ei O(n²). Kun alkio poistetaan, sen odottama vastaus on löytynyt.
# Monotonic increasing stack (bottom to top: smallest to largest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] > val:
stack.pop() # maintain increasing invariant
stack.append(val)
print('Increasing stack (left-to-right):', stack) # [1, 1, 2, 6]
# Monotonic decreasing stack (bottom to top: largest to smallest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] < val:
stack.pop() # maintain decreasing invariant
stack.append(val)
print('Decreasing stack (left-to-right):', stack) # [9, 6]Seuraava suurempi alkio I
Seuraava suurempi alkio -ongelmassa etsitään jokaiselle alkiolle ensimmäinen sen oikealla puolella oleva suurempi alkio. Raakavoimainen O(n²):n kaksoissilmukka on liian hidas. Monotonisen laskevan pinon avulla ongelma ratkaistaan ajassa O(n).
Alkiot käsitellään vasemmalta oikealle. Ennen alkion i lisäämistä pinoon pinosta poistetaan kaikki alkiot, jotka ovat pienempiä kuin nums[i] — nums[i] on niiden kaikkien seuraava suurempi alkio. Kun kaikki alkiot on käsitelty, pinossa jäljellä olevilla alkioilla ei ole oikealla puolellaan suurempaa alkiota (answer = -1).
def next_greater_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # stores indices; stack values are decreasing
for i in range(n):
# Pop elements smaller than nums[i]
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i] # nums[i] is next greater for idx
stack.append(i)
# Remaining elements in stack have no next greater => keep -1
return result
nums = [2, 1, 2, 4, 3]
print(next_greater_element(nums)) # [4, 2, 4, -1, -1]
nums2 = [1, 3, 2, 4]
print(next_greater_element(nums2)) # [3, 4, 4, -1]Seuraava suurempi alkio: algoritmin vaiheittainen läpikäynti
Käydään [2, 1, 2, 4, 3] vaihe vaiheelta läpi. Ylläpidämme indeksien laskevaa pinoa, jossa ovat alkiot, joiden seuraavaa suurempaa alkiota ei ole vielä löydetty.
- i=0, val=2: pino on tyhjä, lisätään 0 pinoon. Pino: [0]
- i=1, val=1: 1 < nums[0]=2, lisätään 1 pinoon. Pino: [0,1]
- i=2, val=2: poistetaan 1 pinosta (nums[1]=1 < 2), result[1]=2; nyt nums[0]=2 ei ole pienempi kuin 2, joten lisätään 2 pinoon. Pino: [0,2]
- i=3, val=4: poistetaan 2 pinosta (result[2]=4), poistetaan 0 pinosta (result[0]=4), lisätään 3 pinoon. Pino: [3]
- i=4, val=3: 3 < nums[3]=4, lisätään 4 pinoon. Pino: [3,4]
- Lopuksi pinon [3,4] alkioille jää result=-1
def next_greater_trace(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(n):
print(f'i={i} val={nums[i]}: stack={[nums[s] for s in stack]}', end=' => ')
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
print(f'pop {nums[idx]}, NGE={nums[i]};', end=' ')
stack.append(i)
print(f'push {nums[i]}, stack={[nums[s] for s in stack]}')
print('Result:', result)
return result
next_greater_trace([2, 1, 2, 4, 3])Edellinen pienempi alkio
Monotonisilla pinoilla voidaan ratkaista myös edellistä pienempää alkiota (PSE) koskevia kyselyitä: kullekin alkiolle etsitään lähin sitä vasemmalla oleva pienempi alkio. Sen sijaan että poistaisimme pinosta suuremman alkion kohdatessamme, poistamme pinosta suuremman tai yhtä suuren alkion ja tallennamme pinon huipun PSE:ksi ennen alkion lisäämistä pinoon.
Suunta muuttuu: käsittelemme alkiot edelleen vasemmalta oikealle, mutta sen sijaan että vastaisimme kyselyihin poistamisen yhteydessä, vastaamme niihin juuri ennen pinoon lisäämistä. Pinohuippu on tuolloin lähin vasemmalla oleva pienempi alkio. Jos pino on tyhjä, vasemmalla ei ole pienempää alkiota (vastaus = -1 tai sentinelli).
def previous_smaller_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # monotonic increasing (values increase bottom to top)
for i in range(n):
# Pop elements >= current (maintain strictly increasing invariant)
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
# Top of stack is previous smaller element (if exists)
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
nums = [4, 5, 2, 10, 8]
print('PSE:', previous_smaller_element(nums)) # [-1, 4, -1, 2, 2]
nums2 = [1, 3, 2, 5, 4]
print('PSE:', previous_smaller_element(nums2)) # [-1, 1, 1, 2, 2]Daily Temperatures: lämpimämpien päivien odottaminen
Daily Temperatures -ongelmassa (LeetCode 739) annetaan päivittäiset lämpötilat ja palautetaan taulukko, jossa kukin alkio kertoo, kuinka monta päivää kuluu lämpimämpään lämpötilaan. Tässä käytetään täsmälleen seuraavan suuremman alkion kaavaa, mutta suuremman arvon sijaan tarvitaan päivien määrä eli indeksien erotus.
Käytetään indeksien monotonisesti laskevaa pinoa. Kun indeksistä i löydetään lämpimämpi lämpötila, poistetaan pinosta kaikki indeksit j, joille temps[j] < temps[i], ja asetetaan result[j] = i - j. Jäljelle jäävillä indekseillä ei ole tulevaisuudessa lämpimämpää päivää (result = 0).
def daily_temperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices of unresolved days
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
j = stack.pop()
result[j] = i - j # days until warmer
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps)) # [1, 1, 4, 2, 1, 1, 0, 0]
temps2 = [30, 40, 50, 60]
print(daily_temperatures(temps2)) # [1, 1, 1, 0] (always warmer next day)
temps3 = [30, 60, 90]
print(daily_temperatures(temps3)) # [1, 1, 0]Kasvava vai laskeva pino: milloin kumpaakin käytetään
Pinon suunnan valinta on ratkaisevaa:
- Monotonisesti laskeva pino (poistetaan, kun nykyinen > huippu): ratkaisee seuraavan suuremman alkion ja edellisen suuremman alkion kyselyt. Sitä käytetään ongelmissa daily-temperatures, largest-rectangle ja trap-rain-water.
- Monotonisesti kasvava pino (poistetaan, kun nykyinen < huippu): ratkaisee seuraavan pienemmän alkion ja edellisen pienemmän alkion kyselyt. Sitä käytetään osakehintojen span-arvon sekä jonossa näkyvien ihmisten määrän etsimiseen.
Muistakaa: pinosta poistamisen aiheuttava alkio on poistettavan alkion kyselyn vastaus — joko seuraava suurempi tai seuraava pienempi alkio sen mukaan, mitä invarianttia ylläpidätte.
# Summary: which stack type for which query?
queries = {
'Next Greater Element': 'Decreasing stack (pop when new > top)',
'Next Smaller Element': 'Increasing stack (pop when new < top)',
'Previous Greater Element': 'Decreasing stack (answer = top before push)',
'Previous Smaller Element': 'Increasing stack (answer = top before push)',
}
for query, approach in queries.items():
print(f'{query}:\n => {approach}\n')
# Mnemonic:
# NGE/PGE => decreasing stack (we pop smaller elements, finding their next/prev larger)
# NSE/PSE => increasing stack (we pop larger elements, finding their next/prev smaller)Seuraava suurempi alkio ympyrätaulukossa
Next Greater Element II (LeetCode 503): annettuna on ympyrätaulukko, jossa taulukon lopusta siirrytään takaisin alkuun, ja tehtävänä on etsiä seuraava suurempi alkio. Temppu on käsitellä taulukko kahdesti ikään kuin indeksit olisi kaksinkertaistettu: iteroidaan välillä 0–2n-1 ja käytetään index % n -laskentaa ympyrätaulukon kiertämiseen. Pinoon lisätään vain indeksit väliltä 0–n-1 (ensimmäisellä kierroksella), jotta samoja indeksejä ei käsitellä kahdesti.
Vaihtoehtoisesti toisella kierroksella voidaan käsitellä taulukko lisäämättä pinoon uusia indeksejä — tällöin pinosta poistetaan vain alkioita. Tämä käsittelee ympyrätaulukon ennakoinnin oikein ilman taulukon todellista monistamista ja säilyttää tilavaativuuden muodossa O(n).
def next_greater_element_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
idx = stack.pop()
result[idx] = nums[i % n]
if i < n:
stack.append(i) # only push real indices (0..n-1)
return result
print(next_greater_element_circular([1, 2, 1])) # [2, -1, 2]
print(next_greater_element_circular([1, 2, 3, 4, 3])) # [2, 3, 4, -1, 4]
print(next_greater_element_circular([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]Osakkeiden span-arvon ongelma
Stock Span -ongelmassa annetaan päivittäiset osakehinnat ja lasketaan kullekin päivälle sen span-arvo — sellaisten peräkkäisten edeltävien päivien määrä, joiden hinta on enintään kyseisen päivän hinta. Pohjimmiltaan kyseessä on edellistä suurempaa alkiota koskeva ongelma: span-arvo on etäisyys tästä päivästä lähimpään päivään, jonka hinta on aidosti suurempi.
Käytetään monotonisesti laskevaa pinoa. Kun käsitellään päivää i, poistetaan pinosta kaikki päivät, joiden hinta on ≤ nykyinen hinta. Span-arvo on i - stack[-1], jos pino ei ole tyhjä, tai i + 1, jos pino on tyhjä (hinta on tähän asti suurin). Tämän jälkeen lisätään i pinoon.
def stock_span(prices):
spans = []
stack = [] # indices of prices forming decreasing sequence
for i, price in enumerate(prices):
while stack and prices[stack[-1]] <= price:
stack.pop()
span = i - stack[-1] if stack else i + 1
spans.append(span)
stack.append(i)
return spans
prices = [100, 80, 60, 70, 60, 75, 85]
print('Prices:', prices)
print('Spans: ', stock_span(prices)) # [1, 1, 1, 2, 1, 4, 6]
# Verification for day 5 (price=75): prev higher is day 1 (80), span = 5-1 = 4
# Day 6 (price=85): prev higher is day 0 (100), span = 6-0 = 6Jonossa näkyvien ihmisten monotoninen pino
Number of Visible People in a Queue -ongelmassa ihmiset seisovat jonossa ja jokaisella on oma pituutensa. Henkilö i näkee henkilön j (j > i), jos kaikki heidän välillään olevat ihmiset ovat lyhyempiä kuin molemmat. Ratkaisussa käytetään monotonisesti laskevaa pinoa.
Käsitellään henkilöt oikealta vasemmalle. Ylläpidetään korkeuksien laskevaa pinoa. Kullekin henkilölle lasketaan näkyvien ihmisten määrä: pinosta poistetaan kaikki lyhyemmät ihmiset (he näkyvät, mutta poistamisen jälkeen he eivät enää rajoita näkyvyyttä), minkä lisäksi lasketaan yksi, jos pino ei ole poistamisen jälkeen tyhjä (ensimmäinen pidempi henkilö näkyy myös). Kokonaisaikavaativuus on O(n), koska jokainen henkilö lisätään pinoon ja poistetaan siitä enintään kerran.
def visible_people(heights):
n = len(heights)
result = [0] * n
stack = [] # decreasing monotonic stack (heights)
for i in range(n - 1, -1, -1): # right to left
count = 0
while stack and stack[-1] < heights[i]:
stack.pop()
count += 1 # can see this shorter person
if stack:
count += 1 # can see the first person >= heights[i]
result[i] = count
stack.append(heights[i])
return result
heights = [10, 6, 8, 5, 11, 9]
print('Heights:', heights)
print('Visible:', visible_people(heights)) # [3, 1, 2, 1, 1, 0]O(n)-takuu: miksi jokainen alkio lisätään ja poistetaan pinosta enintään kerran
Monotonisten pinoalgoritmien O(n)-aikavaatimus perustuu yksinkertaiseen amortisoituun analyysiin: jokainen alkio lisätään pinoon täsmälleen kerran ja poistetaan siitä enintään kerran. Mitään alkiota ei voida lisätä tai poistaa useammin kuin kerran. Siksi kaikkien silmukoiden yhteenlaskettu pinoon lisäämisten ja poistamisten määrä on enintään 2n, joten kokonaisaikavaativuus on O(n), vaikka sisäkkäinen while-silmukka saattaa näyttää viittaavan aikavaativuuteen O(n²).
Tämä amortisoitu analyysi on tärkeää osata perustella työhaastatteluissa. While-silmukka ei suoritu n kertaa jokaisella iteraatiolla — se suoritetaan vain niin kauan, että pinossa odottaneet alkiot saadaan poistettua, ja poistetut alkiot ovat sen jälkeen lopullisesti poissa.
def next_greater_instrumented(nums):
result = [-1] * len(nums)
stack = []
pushes = pops = 0
for i in range(len(nums)):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
pops += 1
stack.append(i)
pushes += 1
print(f'n={len(nums)}, pushes={pushes}, pops={pops}')
print(f'Total operations = {pushes + pops} <= 2n = {2*len(nums)}')
return result
import random
nums = random.sample(range(1000), 100)
next_greater_instrumented(nums)
# Confirm: total operations always <= 2nMonotonisen pinon ongelmien tunnistaminen
Ongelma tarvitsee todennäköisesti monotonisen pinon, jos siinä etsitään lähintä suurempaa tai pienempää alkiota, hintojen span-arvoja, jonossa näkyviä alkioita tai histogrammipohjaisia pinta-aloja. Etsikää tällaisia avainsanoja ja rakenteita: jokaisen alkion vastaus saadaan lähimmältä merkitykselliseltä alkiolta toisessa suunnassa, vasemmalla tai oikealla.
Jos brute-force-ratkaisu käy jokaisen alkion kohdalla vasemmalle tai oikealle (O(n²)), korvatkaa kyseinen läpikäynti monotonisella pinolla. Pino ”muistaa” ehdokkaat, hylkää epäolennaiset vaihtoehdot ja poistaa oikean vastauksen juuri sillä hetkellä, kun sitä tarvitaan.
# Monotonic stack problem recognition guide
patterns = [
('Next/previous greater element', 'Decreasing stack; answer found on pop'),
('Next/previous smaller element', 'Increasing stack; answer found on pop'),
('Days until warmer/colder', 'Stack of indices; answer = i - j'),
('Stock span', 'Decreasing stack; span = i - prev larger idx'),
('Largest rectangle in histogram', 'Increasing stack; area computed on pop'),
('Trapping rain water', 'Decreasing stack or two-pointer'),
('Sliding window maximum', 'Decreasing deque of indices'),
]
print('Monotonic Stack / Deque Pattern Guide:')
print('='*60)
for problem, approach in patterns:
print(f'Problem: {problem}')
print(f' Approach: {approach}')
print()Pikatarkistus
Testatkaa, miten hallitsette tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -kurssin käsitteet.
Oppitunnin kertaus
Tässä oppitunnissa opitte: monotoninen pino säilyttää kasvavan tai laskevan järjestyksen poistamalla invarianttia rikkovat alkiot ennen niiden lisäämistä pinoon, laskeva pino ratkaisee seuraavaa ja edellistä suurempaa alkiota koskevat kyselyt, kun taas kasvava pino ratkaisee seuraavaa ja edellistä pienempää alkiota koskevat kyselyt, ja jokainen alkio lisätään ja poistetaan pinosta enintään kerran, joten kokonaisaika on O(n) — ei O(n²). Seuraavaksi sovellamme monotonista pinoa histogrammin suurimman suorakulmion etsimiseen.
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 ”Monotoninen pino: kasvava ja vähenevä” ilmainen?
Kyllä – oppitunnin ”Monotoninen pino: kasvava ja vähenevä” 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 ”Monotoninen pino: kasvava ja vähenevä”?
Ylläpitäkää kasvavaa tai vähenevää pinoa, jotta voitte vastata seuraavaa suurempaa ja edellistä pienempää alkiota koskeviin kyselyihin tehokkaasti 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 1/4.
Kuinka kauan ”Monotoninen pino: kasvava ja vähenevä”-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