Tumpukan Monotonik: Menaik vs Menurun
Pertahankan tumpukan menaik atau menurun untuk menjawab kueri elemen-lebih-besar-berikutnya dan elemen-lebih-kecil-sebelumnya secara efisien dalam O(n)
Tumpukan Monotonik: Menaik vs Menurun adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 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.
Apa Itu Tumpukan Monoton?
Tumpukan monoton adalah tumpukan yang mempertahankan urutan elemen yang terurut, baik selalu menaik dari bawah ke atas maupun selalu menurun. Sebelum memasukkan elemen baru, kita melakukan pop pada semua elemen yang melanggar invarian monoton. Struktur terbatas ini memungkinkan solusi O(n) untuk persoalan yang jika tidak demikian memerlukan perulangan bersarang O(n²).
Wawasan utamanya: setiap elemen dimasukkan dan di-pop paling banyak sekali, sehingga jumlah operasi di seluruh penelusuran larik adalah O(n), bukan O(n²). Saat kita melakukan pop pada sebuah elemen, kita telah menemukan jawaban yang sedang ditunggunya.
# 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]Elemen Lebih Besar Berikutnya I
Persoalan Elemen Lebih Besar Berikutnya: untuk setiap elemen, temukan elemen pertama di sebelah kanannya yang lebih besar. Perulangan ganda langsung O(n²) terlalu lambat. Dengan tumpukan monoton menurun, kita dapat menyelesaikannya dalam O(n).
Proses elemen dari kiri ke kanan. Sebelum memasukkan elemen i, lakukan pop pada semua elemen dari tumpukan yang lebih kecil daripada nums[i] — nums[i] adalah elemen lebih besar berikutnya bagi semuanya. Setelah semua elemen diproses, elemen yang tersisa di tumpukan tidak memiliki elemen yang lebih besar di sebelah kanannya (jawaban = -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]Elemen Lebih Besar Berikutnya: Menelusuri Algoritme
Mari kita menelusuri [2, 1, 2, 4, 3] langkah demi langkah. Kita mempertahankan tumpukan menurun berisi indeks yang elemen lebih besar berikutnya belum ditemukan.
- i=0, nilai=2: tumpukan kosong, masukkan 0. Tumpukan: [0]
- i=1, nilai=1: 1 < nums[0]=2, masukkan 1. Tumpukan: [0,1]
- i=2, nilai=2: lakukan pop pada 1 (nums[1]=1 < 2), hasil[1]=2; sekarang nums[0]=2 tidak < 2, masukkan 2. Tumpukan: [0,2]
- i=3, nilai=4: lakukan pop pada 2 (hasil[2]=4), lakukan pop pada 0 (hasil[0]=4), masukkan 3. Tumpukan: [3]
- i=4, nilai=3: 3 < nums[3]=4, masukkan 4. Tumpukan: [3,4]
- Selesai: tumpukan [3,4] memiliki hasil=-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])Elemen Lebih Kecil Sebelumnya
Tumpukan monoton juga dapat menjawab kueri elemen lebih kecil sebelumnya (PSE): untuk setiap elemen, elemen terdekat di sebelah kirinya yang lebih kecil. Alih-alih melakukan pop ketika menemukan elemen yang lebih besar, kita melakukan pop ketika menemukan elemen yang lebih besar atau sama, lalu mencatat puncak tumpukan sebagai PSE sebelum memasukkan elemen saat ini.
Arahnya berubah: kita tetap memproses dari kiri ke kanan, tetapi alih-alih menjawab pertanyaan saat melakukan pop, kita menjawabnya tepat sebelum memasukkan elemen. Puncak tumpukan pada saat itu adalah elemen lebih kecil terdekat di sebelah kiri. Jika tumpukan kosong, tidak ada elemen yang lebih kecil di sebelah kiri (jawaban = -1 atau penanda).
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]Suhu Harian: Menunggu Hari yang Lebih Hangat
Masalah Suhu Harian (LeetCode 739): diberikan suhu harian, kembalikan larik yang setiap elemennya adalah jumlah hari hingga suhu yang lebih hangat. Ini persis pola elemen lebih besar berikutnya, tetapi alih-alih nilai yang lebih besar, kita menginginkan jumlah hari (selisih indeks).
Gunakan tumpukan menurun monoton berisi indeks. Ketika menemukan suhu yang lebih hangat pada indeks i, lakukan pop pada semua indeks j dari tumpukan yang memenuhi temps[j] < temps[i] dan tetapkan result[j] = i - j. Indeks yang tersisa tidak memiliki hari yang lebih hangat di masa mendatang (hasil = 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]Tumpukan Meningkat vs Menurun: Kapan Menggunakan Masing-Masingnya
Memilih arah tumpukan yang tepat sangat penting:
- Tumpukan monoton menurun (lakukan pop ketika nilai saat ini > puncak): menjawab kueri elemen lebih besar berikutnya dan elemen lebih besar sebelumnya. Digunakan dalam masalah suhu harian, persegi panjang terbesar, dan penampungan air hujan.
- Tumpukan monoton meningkat (lakukan pop ketika nilai saat ini < puncak): menjawab kueri elemen lebih kecil berikutnya dan elemen lebih kecil sebelumnya. Digunakan untuk mencari rentang harga saham dan jumlah orang yang terlihat dalam antrean.
Ingat: elemen yang menyebabkan pop adalah jawaban untuk kueri elemen yang dikeluarkan — bisa berupa elemen lebih besar berikutnya atau elemen lebih kecil berikutnya, bergantung pada invarian yang Anda pertahankan.
# 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)Elemen Lebih Besar Berikutnya Melingkar
Elemen Lebih Besar Berikutnya II (LeetCode 503): diberikan larik melingkar (berputar kembali ke awal), temukan elemen lebih besar berikutnya. Triknya adalah memproses larik dua kali dengan menggandakan indeks: lakukan iterasi dari 0 hingga 2n-1, menggunakan index % n untuk berputar kembali ke awal. Kita hanya memasukkan indeks dari 0 hingga n-1 (lintasan pertama) agar tidak menghitung elemen dua kali.
Alternatifnya, proses larik pada lintasan kedua tanpa memasukkan indeks baru — hanya melakukan pop. Cara ini menangani pencarian melingkar ke depan dengan benar tanpa benar-benar menggandakan larik, sehingga penggunaan ruang tetap 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]Masalah Rentang Harga Saham
Masalah Rentang Harga Saham: diberikan harga saham harian, hitung rentang setiap hari — jumlah hari berturut-turut sebelumnya yang harganya kurang dari atau sama dengan harga hari ini. Ini sebenarnya adalah masalah elemen lebih besar sebelumnya: rentang adalah jarak dari hari ini kembali ke hari terdekat yang memiliki harga lebih tinggi secara ketat.
Gunakan tumpukan menurun monoton. Saat memproses hari i, lakukan pop pada semua hari yang harganya ≤ harga saat ini. Rentangnya adalah i - stack[-1] jika tumpukan tidak kosong, atau i + 1 jika kosong (harga saat ini adalah yang tertinggi sejauh ini). Kemudian masukkan i.
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 = 6Tumpukan Monoton untuk Orang yang Terlihat dalam Antrean
Masalah Jumlah Orang yang Terlihat dalam Antrean: orang-orang berdiri dalam sebuah antrean, masing-masing memiliki tinggi badan. Orang i dapat melihat orang j (j > i) jika semua orang di antara mereka lebih pendek daripada keduanya. Masalah ini menggunakan tumpukan menurun monoton.
Proses dari kanan ke kiri. Pertahankan tumpukan menurun berisi tinggi badan. Untuk setiap orang, hitung berapa banyak orang yang dapat dilihatnya: lakukan pop pada semua orang yang lebih pendek (terlihat, tetapi kemudian terhalang), lalu tambahkan 1 jika tumpukan masih tidak kosong (orang pertama yang lebih tinggi juga terlihat). Secara keseluruhan, ini menghasilkan O(n) karena setiap orang dimasukkan dan dikenai pop paling banyak satu kali.
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]Jaminan O(n): Mengapa Setiap Elemen Dimasukkan dan Dikeluarkan Paling Banyak Satu Kali
Jaminan waktu O(n) dari algoritme tumpukan monoton berasal dari argumen amortisasi sederhana: setiap elemen dimasukkan ke tumpukan tepat satu kali dan dikenai pop paling banyak satu kali. Tidak ada elemen yang dapat dimasukkan atau dikenai pop lebih dari satu kali. Oleh karena itu, jumlah total operasi memasukkan + pop di seluruh perulangan paling banyak 2n, sehingga total pekerjaan adalah O(n), meskipun perulangan while bersarang tampak menunjukkan O(n²).
Analisis amortisasi ini penting untuk dijelaskan dalam wawancara. Perulangan while tidak berjalan n kali pada setiap iterasi — perulangan itu hanya berjalan sebanyak yang diperlukan untuk mengeluarkan elemen yang sedang menunggu, dan elemen-elemen tersebut tidak akan pernah kembali setelah dikeluarkan.
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 <= 2nMengenali Masalah Tumpukan Monoton
Sebuah masalah kemungkinan membutuhkan tumpukan monoton jika meminta elemen lebih besar atau lebih kecil terdekat, rentang harga, elemen yang terlihat dalam satu baris, atau area berbasis histogram. Carilah kata kunci dan pola berikut: setiap elemen membutuhkan jawaban dari elemen relevan terdekat dalam salah satu arah (kiri atau kanan).
Jika solusi coba semua kemungkinan memindai ke kiri atau ke kanan dari setiap elemen (O(n²)), gantilah pemindaian tersebut dengan tumpukan monoton. Tumpukan tersebut “mengingat” jawaban kandidat, membuang jawaban yang tidak relevan, dan mengeluarkan jawaban yang tepat pada saat dibutuhkan.
# 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()Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritme — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda mempelajari bahwa: tumpukan monoton mempertahankan urutan meningkat atau menurun dengan mengeluarkan elemen yang melanggar invarian sebelum memasukkan elemen baru, tumpukan menurun menjawab elemen lebih besar berikutnya/sebelumnya, sedangkan tumpukan meningkat menjawab elemen lebih kecil berikutnya/sebelumnya, dan setiap elemen dimasukkan dan dikeluarkan paling banyak satu kali sehingga total waktunya O(n) — bukan O(n²). Selanjutnya, kita akan menerapkan tumpukan monoton untuk menemukan persegi panjang terbesar dalam histogram.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Tumpukan Monotonik: Menaik vs Menurun” gratis?
Ya — teks lengkap “Tumpukan Monotonik: Menaik vs Menurun” 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 “Tumpukan Monotonik: Menaik vs Menurun”?
Pertahankan tumpukan menaik atau menurun untuk menjawab kueri elemen-lebih-besar-berikutnya dan elemen-lebih-kecil-sebelumnya secara efisien dalam O(n) 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 1 dari 4.
Berapa lama pelajaran “Tumpukan Monotonik: Menaik vs Menurun” 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
- Tumpukan Monotonik: Menaik vs Menurun
- Persegi Panjang Terbesar dalam Histogram
- Maksimum Jendela Geser dengan Deque Monotonik
- Menampung Air Hujan: Tumpukan dan Dua Penunjuk