Monotoninen pino: seuraava suurempi alkio
Vastaa jännekyselyihin yhdellä läpikäynnillä
Monotoninen pino: seuraava suurempi alkio 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.
Seuraavan suuremman etsiminen
Jokaiselle luvulle halutaan ensimmäinen sitä suurempi arvo oikealta. Brute force vaatii ajan O(n²), mutta monotoninen pino ratkaisee tehtävän yhdellä läpikäynnillä.
Mitä monotoninen tarkoittaa
Monotoninen pino pitää arvonsa järjestyksessä, tässä tapauksessa laskevassa järjestyksessä. Kun järjestys olisi rikkoutumassa, tiedämme löytäneemme vastauksen.
Tallenna indeksit, älä arvoja
Työnnä pinoon raakojen lukujen sijaan indeksit. Näin tiedät tarkalleen, minkä kohdan voit täyttää, kun suurempi alkio löytyy.
stack = []
ans = [-1] * len(nums)Käy vasemmalta oikealle
Käy taulukko kerran läpi. Jokaisessa indeksissä joko poistat jo ratkaistuja alkioita pinosta tai työnnät nykyisen indeksin pinoon myöhempää käsittelyä varten.
for i in range(len(nums)):Poista pienemmät
Niin kauan kuin nykyinen arvo päihittää päällimmäisen indeksin kohdalla olevan arvon, kyseinen päällimmäinen alkio on viimein löytänyt seuraavan suuremman alkionsa.
while stack and nums[i] > nums[stack[-1]]:Tallenna vastaus
Poista päällimmäinen indeksi ja aseta sen vastaukseksi nykyinen arvo. Jokainen indeksi ratkaistaan täsmälleen kerran, joten työmäärä pysyy lineaarisena.
j = stack.pop()
ans[j] = nums[i]Työnnä pinoon ja jatka
Kun kaikki pienemmät alkiot on ratkaistu, työnnä nykyinen indeksi pinoon odottamaan omaa tulevaa suurempaa alkiotaan.
stack.append(i)Jäljelle jääneillä ei ole vastausta
Lopussa pinoon jääneet indeksit eivät koskaan kohdanneet suurempaa arvoa. Niille jää oletusarvoksi -1, mikä tarkoittaa, ettei suurempaa arvoa ole.
Miksi aika on O(n)
Jokainen indeksi työnnetään pinoon kerran ja poistetaan kerran. Sisemmästä while-silmukasta huolimatta kokonais työmäärä pysyy lineaarisena koko läpikäynnin ajan.
Käännä vertailu seuraavaa pienempää varten
Tarvitsetko seuraavan pienemmän alkion? Pidä pino kasvavana vaihtamalla vertailu suuremmasta pienempään.
while stack and nums[i] < nums[stack[-1]]:Malli, ei temppu
Välikyselyissä, osakehinnoissa ja histogrammien pinta-aloissa käytetään samaa ideaa. Monotoninen pino on keskeinen kilpailuohjelmoinnin malli, joka kannattaa opetella ulkoa.
Pikakysymys
Ratkaiset seuraavan suuremman alkion etsimisen monotonisella pinolla. Miksi kokonaisaika on lineaarinen?
Kertaus: yksi läpikäynti, monta vastausta
Käytit indeksien laskevaa monotonista pinoa löytääksesi seuraavat suuremmat alkiot ajassa O(n). Tämä malli avaa tien moniin välikyselytehtäviin. 🚀
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: seuraava suurempi alkio” ilmainen?
Kyllä – oppitunnin ”Monotoninen pino: seuraava suurempi alkio” 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: seuraava suurempi alkio”?
Vastaa jännekyselyihin 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 ”Monotoninen pino: seuraava suurempi alkio”-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
- Pinot sulkevien sulkeiden tarkistamiseen
- Monotoninen pino: seuraava suurempi alkio
- Jonot ja collections.deque
- Liukuva ikkunan maksimi dequella