Corak Tindanan Monotonik
Gunakan tindanan monotonik untuk menyelesaikan daily-temperatures, largest-rectangle-in-histogram dan next-greater-element dalam O(n).
Corak Tindanan Monotonik ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 3 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah Tindanan Monotonik?
Tindanan monotonik ialah tindanan yang mengekalkan invarian tersusun antara elemennya. Tindanan monotonik menaik mempunyai elemen yang meningkat dari bawah ke atas; tindanan monotonik menurun mempunyai elemen yang menurun dari bawah ke atas. Apabila elemen baharu melanggar invarian tersebut, elemen akan dikeluarkan melalui pop sehingga invarian dipulihkan, kemudian elemen baharu itu dimasukkan melalui push.
Mekanisme ringkas ini membolehkan jawapan O(n) bagi pertanyaan tentang “elemen lebih besar terdekat” dan “elemen lebih kecil terdekat”, yang secara naif memerlukan gelung 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 Seterusnya (LeetCode 496)
Bagi setiap elemen, cari elemen pertama di sebelah kanannya yang benar-benar lebih besar. Kaedah cuba habis-habisan O(n²) mengimbas ke kanan dari setiap kedudukan. Pendekatan tindanan monotonik: kekalkan tindanan menurun yang mengandungi indeks. Apabila elemen yang lebih besar ditemui, lakukan pop pada semua indeks yang lebih kecil — “elemen lebih besar seterusnya” bagi indeks tersebut ialah elemen semasa. Indeks yang masih tinggal tidak mempunyai elemen lebih besar seterusnya (jawapannya ialah -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 Seterusnya dalam Tatasusunan Melingkar
LeetCode 503 “Next Greater Element II”: masalah yang sama, tetapi tatasusunan dianggap melingkar. Selepas sampai ke penghujung, kembali ke awal dan lakukan semakan dari sana. Helahnya ialah mengulang tatasusunan dua kali (indeks 0 hingga 2n-1) dan menggunakan i % n untuk mengindeks tatasusunan asal. Hanya lakukan push pada indeks dalam julat [0, n-1] untuk mengelakkan pemprosesan pendua.
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: Penyelesaian Lengkap
LeetCode 739 sekali lagi: bagi setiap hari, berapa hari perlu ditunggu sehingga suhu menjadi lebih panas? Tindanan monotonik menyimpan indeks hari dengan suhu dalam tertib menurun. Apabila hari i yang lebih panas ditemui, lakukan pop pada semua indeks hari yang lebih sejuk j daripada tindanan dan catat result[j] = i - j. Hari yang masih tinggal dalam tindanan tidak pernah menemui hari yang lebih panas, jadi keputusannya kekal 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 “elemen lebih kecil sebelumnya” bermaksud: bagi setiap elemen, apakah nilai lebih kecil yang paling hampir di sebelah kirinya? Gunakan tindanan monotonik menaik dengan memproses elemen dari kiri ke kanan. Sebelum melakukan push pada indeks i, bahagian atas tindanan ialah elemen lebih kecil sebelumnya, kerana semua elemen yang lebih besar daripada nums[i] telah dikeluarkan melalui pop semasa penyisipan terdahulu yang menyebabkan elemen tersebut dikeluarkan.
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]Segi Empat Terbesar dalam Histogram
LeetCode 84 “Largest Rectangle in Histogram”: gunakan tindanan indeks yang menaik secara monotonik. Bagi setiap palang, lakukan pop pada semua palang yang lebih tinggi daripada palang semasa. Bagi setiap palang yang dikeluarkan, h, sempadan kanannya ialah indeks semasa i dan sempadan kirinya ialah bahagian atas tindanan yang baharu + 1 (atau 0 jika tindanan kosong). Luas = h × (kanan - kiri). Lakukan append pada penanda dengan tinggi 0 untuk memaksa semua palang yang masih tinggal dikeluarkan pada penghujungnya.
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])) # 1Segi Empat Maksimum (LeetCode 85)
LeetCode 85 “Maximal Rectangle” mengembangkan masalah histogram kepada matriks perduaan 2D. Bagi setiap baris, kira ketinggian palang terkumpul: jika matrix[row][col] == '1', ketinggiannya ialah bilangan 1 berturutan di atas dan termasuk sel ini. Kemudian gunakan algoritma “segi empat terbesar dalam histogram” pada tatasusunan ketinggian bagi setiap baris. Masa: O(m × n) untuk matriks 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)) # 6Air Hujan Terperangkap: Pendekatan Tindanan
LeetCode 42 “Trapping Rain Water” dengan tindanan: kekalkan tindanan indeks yang menurun. Apabila palang yang lebih tinggi ditemui, sebuah lembah terbentuk. Keluarkan dasar lembah melalui pop; kira lebar air sebagai (current_index - stack_top - 1) dan ketinggian sebagai (min(current_bar, new_stack_top_bar) - valley_height). Jumlahkan semua sumbangan. Masa: 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])) # 9Mengenal Pasti Masalah Tindanan Monotonik
Petunjuk bahawa tindanan monotonik ialah alat yang sesuai: masalah meminta elemen lebih besar atau lebih kecil yang seterusnya atau sebelumnya, jawapan bagi setiap elemen bergantung pada elemen dalam arah tertentu, atau penyelesaian naif O(n²) melibatkan pengimbasan ke kiri atau kanan bagi setiap elemen. Tindanan menyimpan calon yang mungkin menjadi jawapan bagi elemen akan datang dan membuangnya sebaik sahaja calon yang lebih baik muncul.
Sentiasa tentukan terlebih dahulu: menaik (untuk elemen lebih kecil seterusnya/sebelumnya) atau menurun (untuk elemen lebih besar seterusnya/sebelumnya), serta dari arah mana anda akan memproses elemen.
Analisis O(n) Teramortisasi
Algoritma tindanan monotonik kelihatan seperti O(n log n) atau O(n)² pada mulanya kerana terdapat gelung sementara di dalam gelung untuk. Namun, setiap elemen hanya menjalani push sekali dan pop sekali paling banyak. Jumlah operasi push ialah n, dan jumlah operasi pop juga tidak melebihi n. Oleh itu, merentasi semua lelaran, jumlah kerja ialah 2n operasi — O(n) secara teramortisasi, bukannya 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*nRingkasan: Pilihan Invarian Tindanan Monotonik
Pilih arah tindanan berdasarkan pertanyaan. Untuk elemen lebih besar seterusnya, gunakan tindanan menurun — lakukan pop apabila elemen semasa lebih besar. Untuk elemen lebih kecil seterusnya, gunakan tindanan menaik — lakukan pop apabila elemen semasa lebih kecil. Untuk segi empat terbesar, gunakan tindanan menaik dan lakukan pop apabila palang yang lebih pendek muncul. Untuk nilai maksimum tetingkap gelongsor, gunakan baris gilir dua hujung menurun dan keluarkan elemen dari kedua-dua hujung.
Menulis invarian dalam ulasan sebelum menulis kod menjelaskan logik dan mempercepat penyahpepijatan.
Semakan Ringkas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Imbas Kembali Pelajaran
Dalam pelajaran ini, anda telah mempelajari bahawa: tindanan monotonik mengekalkan invarian tersusun dengan mengeluarkan melalui pop elemen yang melanggarnya sebelum melakukan push pada elemen baharu, tindanan menurun menjawab pertanyaan elemen lebih besar seterusnya; tindanan menaik menjawab pertanyaan elemen lebih kecil seterusnya, dan jumlah masa ialah O(n) secara teramortisasi kerana setiap elemen menjalani push dan pop paling banyak sekali. Seterusnya, kita akan melaksanakan baris gilir menggunakan tindanan dan tindanan menggunakan baris gilir.
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Corak Tindanan Monotonik” percuma?
Ya — teks penuh “Corak Tindanan Monotonik” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Corak Tindanan Monotonik”?
Gunakan tindanan monotonik untuk menyelesaikan daily-temperatures, largest-rectangle-in-histogram dan next-greater-element dalam O(n). Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 3 daripada 4.
Berapa lamakah pelajaran “Corak Tindanan Monotonik” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Pelaksanaan Tindanan dan Aplikasinya
- Pelaksanaan Baris Gilir dan Deque
- Corak Tindanan Monotonik
- Simulasi Saling Tindanan dan Baris Gilir