Pola Stack Monotonik
Terapkan stack monotonik untuk menyelesaikan daily-temperatures, largest-rectangle-in-histogram, dan next-greater-element dalam O(n).
Pola Stack Monotonik adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 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 invarian terurut pada elemen-elemennya. Tumpukan monoton menaik memiliki elemen yang meningkat dari bawah ke atas; tumpukan monoton menurun memiliki elemen yang menurun dari bawah ke atas. Saat elemen baru melanggar invarian, elemen-elemen dikeluarkan dengan pop sampai invarian kembali terpenuhi, lalu elemen baru ditambahkan dengan push.
Mekanisme sederhana ini memungkinkan diperolehnya jawaban dalam O(n) untuk pertanyaan tentang 'elemen lebih besar terdekat' dan 'elemen lebih kecil terdekat', yang secara naif memerlukan perulangan bersarang O(n²).
# 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)Elemen Lebih Besar Berikutnya (LeetCode 496)
Untuk setiap elemen, temukan elemen pertama di sebelah kanannya yang benar-benar lebih besar. Pendekatan brute force O(n²) memindai ke kanan dari setiap posisi. Pendekatan tumpukan monoton: pertahankan tumpukan menurun yang berisi indeks. Saat elemen yang lebih besar ditemukan, keluarkan semua indeks yang lebih kecil — elemen saat ini adalah 'elemen lebih besar berikutnya' bagi indeks-indeks tersebut. Indeks yang tersisa tidak memiliki elemen lebih besar berikutnya (jawabannya adalah -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]Elemen Lebih Besar Berikutnya dalam Larik Melingkar
LeetCode 503 'Elemen Lebih Besar Berikutnya II': masalah yang sama, tetapi larik diperlakukan sebagai lingkaran. Setelah mencapai akhir, kembali ke awal dan lakukan pemeriksaan dari sana. Triknya: iterasikan larik dua kali (indeks 0 hingga 2n-1) dan gunakan i % n untuk mengakses larik asli. Hanya masukkan indeks dalam rentang [0, n-1] ke tumpukan agar tidak terjadi pemrosesan duplikat.
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]Suhu Harian: Solusi Lengkap
LeetCode 739 dibahas kembali: untuk setiap hari, berapa hari yang diperlukan hingga suhu yang lebih hangat? Tumpukan monoton menyimpan indeks hari dengan suhu dalam urutan menurun. Saat ditemukan hari yang lebih hangat i, keluarkan semua indeks hari yang lebih dingin j dari tumpukan dan catat result[j] = i - j. Hari yang tersisa di tumpukan tidak pernah menemukan hari yang lebih hangat, sehingga hasilnya tetap 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]Elemen Lebih Kecil Sebelumnya
Pertanyaan tentang 'elemen lebih kecil sebelumnya' adalah: untuk setiap elemen, berapa nilai lebih kecil terdekat di sebelah kirinya? Gunakan tumpukan monoton menaik dengan memproses dari kiri ke kanan. Sebelum memasukkan indeks i, elemen teratas tumpukan adalah elemen lebih kecil sebelumnya, karena semua elemen yang lebih besar daripada elemen pada posisi i telah dikeluarkan saat penambahan sebelumnya memicu pengeluaran elemen-elemen tersebut.
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]Persegi Panjang Terbesar dalam Histogram
LeetCode 84 'Persegi Panjang Terbesar dalam Histogram': gunakan tumpukan indeks yang monoton menaik. Untuk setiap batang, keluarkan semua batang yang lebih tinggi daripada batang saat ini. Untuk setiap batang yang dikeluarkan h, batas kanannya adalah indeks saat ini i dan batas kirinya adalah puncak tumpukan yang baru + 1 (atau 0 jika tumpukan kosong). Luas = h × (kanan - kiri). Tambahkan penanda dengan tinggi 0 untuk memaksa semua batang yang tersisa dikeluarkan di akhir.
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])) # 1Persegi Panjang Maksimum (LeetCode 85)
LeetCode 85 'Persegi Panjang Maksimum' memperluas masalah histogram ke matriks biner 2D. Untuk setiap baris, hitung tinggi batang yang terakumulasi: jika matrix[row][col] == '1', tingginya adalah jumlah angka 1 berturut-turut di atas dan termasuk sel ini. Kemudian terapkan algoritma 'persegi panjang terbesar dalam histogram' pada larik tinggi setiap baris. Waktu: O(m × n) untuk matriks berukuran m×n.
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)) # 6Menampung Air Hujan: Pendekatan Tumpukan
LeetCode 42 'Menampung Air Hujan' dengan tumpukan: pertahankan tumpukan indeks yang menurun. Saat ditemukan batang yang lebih tinggi, terbentuk sebuah lembah. Keluarkan dasar lembah; hitung lebar air sebagai (indeks_saat_ini - puncak_tumpukan - 1) dan tingginya sebagai (min(batang_saat_ini, batang_puncak_tumpukan_baru) - tinggi_lembah). Jumlahkan semua kontribusinya. Waktu: O(n), ruang: 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])) # 9Mengenali Masalah Tumpukan Monoton
Tanda-tanda bahwa tumpukan monoton merupakan alat yang tepat: masalah meminta elemen lebih besar atau lebih kecil berikutnya maupun sebelumnya, jawaban untuk setiap elemen bergantung pada elemen-elemen dalam arah tertentu, atau solusi naif O(n²) melibatkan pemindaian ke kiri atau kanan untuk setiap elemen. Tumpukan menyimpan kandidat yang mungkin menjadi jawaban bagi elemen-elemen berikutnya dan membuangnya segera setelah kandidat yang lebih baik tiba.
Selalu tentukan sejak awal: menaik (untuk elemen lebih kecil berikutnya atau sebelumnya) atau menurun (untuk elemen lebih besar berikutnya atau sebelumnya), serta dari arah mana Anda akan memprosesnya.
Analisis Amortisasi O(n)
Algoritma tumpukan monoton sekilas tampak memiliki kompleksitas O(n log n) atau O(n) karena adanya perulangan while di dalam perulangan for. Namun, setiap elemen ditambahkan paling banyak sekali dan dikeluarkan paling banyak sekali. Jumlah total operasi penambahan adalah n, dan jumlah total operasi pengeluaran juga paling banyak n. Jadi, di seluruh iterasi, total pekerjaannya adalah 2n operasi — O(n) secara amortisasi, bukan 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*nRangkuman: Pilihan Invarian Tumpukan Monoton
Pilih arah tumpukan berdasarkan pertanyaannya. Untuk elemen lebih besar berikutnya, gunakan tumpukan menurun — keluarkan elemen saat elemen saat ini lebih besar. Untuk elemen lebih kecil berikutnya, gunakan tumpukan menaik — keluarkan elemen saat elemen saat ini lebih kecil. Untuk persegi panjang terbesar, gunakan tumpukan menaik dan keluarkan elemen saat muncul batang yang lebih pendek. Untuk maksimum jendela geser, gunakan antrean dua ujung menurun dan hapus elemen dari kedua ujung.
Menuliskan invarian dalam komentar sebelum mulai membuat kode akan memperjelas logika dan mempercepat proses pencarian kesalahan.
Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rangkuman Pelajaran
Dalam pelajaran ini Anda mempelajari: tumpukan monoton mempertahankan invarian terurut dengan mengeluarkan elemen yang melanggarnya sebelum menambahkan elemen baru, tumpukan menurun menjawab pertanyaan tentang elemen lebih besar berikutnya; tumpukan menaik menjawab pertanyaan tentang elemen lebih kecil berikutnya, serta waktu totalnya adalah O(n) secara amortisasi karena setiap elemen paling banyak sekali ditambahkan dan dikeluarkan. Selanjutnya, kita akan mengimplementasikan antrean menggunakan tumpukan dan tumpukan menggunakan antrean.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Pola Stack Monotonik” gratis?
Ya — teks lengkap “Pola Stack Monotonik” 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 “Pola Stack Monotonik”?
Terapkan stack monotonik untuk menyelesaikan daily-temperatures, largest-rectangle-in-histogram, dan next-greater-element 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 3 dari 4.
Berapa lama pelajaran “Pola Stack Monotonik” 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
- Implementasi Stack dan Penerapannya
- Implementasi Queue dan Deque
- Pola Stack Monotonik
- Simulasi Saling Menggunakan Stack dan Queue