Stack Monoton: Elemen Lebih Besar Berikutnya
Menjawab pertanyaan rentang dalam satu lintasan
Stack Monoton: Elemen Lebih Besar Berikutnya adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Masalah Elemen Lebih Besar Berikutnya
Untuk setiap bilangan, Anda ingin mencari nilai pertama yang lebih besar di sebelah kanannya. Pencarian menyeluruh memerlukan O(n kuadrat), tetapi tumpukan monoton dapat menyelesaikannya dalam satu lintasan.
Arti Monoton
Tumpukan monoton mempertahankan nilai-nilainya dalam urutan terurut, dalam hal ini menurun, sehingga saat urutan tersebut akan rusak, kita tahu bahwa sebuah jawaban telah ditemukan.
Simpan Indeks, Bukan Nilai
Masukkan indeks, bukan angka mentah. Dengan begitu, Anda tahu persis posisi mana yang harus diisi saat elemen yang lebih besar muncul.
stack = []
ans = [-1] * len(nums)Telusuri dari Kiri ke Kanan
Lakukan iterasi pada larik satu kali. Pada setiap indeks, Anda akan mengeluarkan elemen yang jawabannya sudah ditemukan atau memasukkan indeks saat ini untuk diproses nanti.
for i in range(len(nums)):Keluarkan Elemen yang Lebih Kecil
Selama nilai saat ini mengalahkan nilai pada indeks teratas, elemen teratas tersebut akhirnya telah menemukan elemen lebih besar berikutnya.
while stack and nums[i] > nums[stack[-1]]:Catat Jawabannya
Keluarkan indeks teratas dan tetapkan jawabannya sebagai nilai saat ini. Setiap indeks diselesaikan tepat satu kali, sehingga pekerjaan tetap linear.
j = stack.pop()
ans[j] = nums[i]Masukkan dan Lanjutkan
Setelah menyelesaikan semua elemen yang lebih kecil, masukkan indeks saat ini agar dapat menunggu elemen lebih besar berikutnya.
stack.append(i)Sisa Elemen Tidak Memiliki Jawaban
Indeks yang masih berada di tumpukan pada akhir proses tidak pernah menemukan nilai yang lebih besar. Indeks tersebut mempertahankan nilai bawaan -1, yang berarti tidak ada elemen lebih besar.
Mengapa O(n)
Setiap indeks dimasukkan sekali dan dikeluarkan sekali. Meskipun ada iterasi while di dalamnya, total pekerjaan tetap linear untuk seluruh penelusuran.
Balikkan untuk Elemen Lebih Kecil Berikutnya
Memerlukan elemen lebih kecil berikutnya? Pertahankan tumpukan dalam urutan meningkat dengan membalikkan perbandingan dari lebih besar menjadi lebih kecil.
while stack and nums[i] < nums[stack[-1]]:Sebuah Pola, Bukan Trik
Kueri rentang, harga saham, dan luas histogram semuanya menggunakan kembali gagasan ini. Tumpukan monoton adalah pola inti dalam kompetisi pemrograman yang layak dihafalkan.
Pemeriksaan Singkat
Anda menyelesaikan masalah elemen lebih besar berikutnya dengan tumpukan monoton. Mengapa total waktunya linear?
Ringkasan: Satu Lintasan, Banyak Jawaban
Anda menggunakan tumpukan monoton menurun yang berisi indeks untuk menemukan elemen lebih besar berikutnya dalam O(n). Pola ini membuka jalan untuk banyak masalah rentang. 🚀
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Stack Monoton: Elemen Lebih Besar Berikutnya” gratis?
Ya — teks lengkap “Stack Monoton: Elemen Lebih Besar Berikutnya” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Stack Monoton: Elemen Lebih Besar Berikutnya”?
Menjawab pertanyaan rentang dalam satu lintasan Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Stack Monoton: Elemen Lebih Besar Berikutnya” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Stack untuk Mencocokkan Kurung
- Stack Monoton: Elemen Lebih Besar Berikutnya
- Queue dan collections.deque
- Maksimum Sliding Window dengan Deque