Segi Empat Terbesar dalam Histogram
Gunakan tindanan monoton untuk menjejak sempadan kiri dan mengira luas maksimum segi empat yang muat dalam histogram dalam satu laluan.
Segi Empat Terbesar dalam Histogram ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran DSA Interview Prep, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.
Masalah: Segi Empat Tepat Terbesar dalam Histogram
Masalah Segi Empat Tepat Terbesar dalam Histogram (LeetCode 84) memberikan tatasusunan integer bukan negatif yang mewakili ketinggian batang dalam histogram, dengan setiap batang mempunyai lebar 1. Cari luas segi empat tepat terbesar yang boleh dibentuk dalam histogram. Segi empat tepat itu mesti merangkumi batang berturutan dan ketinggiannya dihadkan oleh batang paling pendek yang diliputinya.
Pendekatan secara cuba habis-habisan: bagi setiap pasangan (i, j), hitung ketinggian minimum dalam [i, j] dan darabkannya dengan (j - i + 1). Ini ialah O(n³), atau O(n²) dengan nilai minimum yang dipraira — terlalu lambat. Penyelesaian tindanan monotonik berjalan dalam O(n).
# Example: heights = [2, 1, 5, 6, 2, 3]
# Rectangles:
# width=1, height=6 at index 3 => area=6
# width=2, height=5 at indices 2-3 => area=10 (maximum!)
# width=6, height=1 across all => area=6
# width=3, height=2 at indices 2-4 => area=6
heights = [2, 1, 5, 6, 2, 3]
print('Heights:', heights)
print('Expected max area: 10 (bars of height 5 and 6, width 2)')
# Brute force for small inputs:
def brute_force(heights):
n = len(heights)
max_area = 0
for i in range(n):
min_h = heights[i]
for j in range(i, n):
min_h = min(min_h, heights[j])
max_area = max(max_area, min_h * (j - i + 1))
return max_area
print('Brute force answer:', brute_force(heights)) # 10Petua Utama: Apakah yang Mengehadkan Segi Empat Tepat Setiap Batang
Bagi setiap batang i dengan ketinggian h, segi empat tepat terbesar yang boleh menjadikan batang itu sebagai minimum memanjang ke kiri sehingga batang pertama yang lebih pendek daripada h, dan ke kanan sehingga batang pertama yang lebih pendek daripada h. Lebarnya ialah right_boundary - left_boundary - 1 dan luasnya ialah h × width.
Ini membingkai semula masalah: bagi setiap batang, cari elemen lebih kecil sebelumnya (PSE) dan elemen lebih kecil seterusnya (NSE). Inilah yang dihitung oleh tindanan monotonik menaik. Saat kita melakukan pop pada batang i (kerana batang yang lebih pendek telah ditemui), batang semasa ialah NSE-nya dan bahagian atas tindanan selepas pop ialah PSE-nya.
heights = [2, 1, 5, 6, 2, 3]
n = len(heights)
# Find PSE and NSE for each bar
pse = [-1] * n # index of previous smaller element
nse = [n] * n # index of next smaller element (default: beyond array)
# PSE
stack = []
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
pse[i] = stack[-1] if stack else -1
stack.append(i)
# NSE
stack = []
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
nse[i] = stack[-1] if stack else n
stack.append(i)
max_area = 0
for i in range(n):
width = nse[i] - pse[i] - 1
area = heights[i] * width
print(f'Bar {i} (h={heights[i]}): PSE={pse[i]}, NSE={nse[i]}, width={width}, area={area}')
max_area = max(max_area, area)
print('Max area:', max_area)Penyelesaian Satu Laluan dengan Tindanan Monotonik
Pendekatan dua laluan di atas berfungsi tetapi boleh digabungkan menjadi satu laluan. Proses batang dari kiri ke kanan dengan tindanan monotonik menaik. Apabila batang i lebih pendek daripada bahagian atas tindanan, lakukan pop pada bahagian atas tindanan — ketinggian batang yang dikeluarkan ialah ketinggian sebuah segi empat tepat, sempadan kanannya ialah i dan sempadan kirinya ialah bahagian atas tindanan baharu + 1.
Helah biasa: append penanda 0 pada penghujung ketinggian. Ini memastikan semua batang dikeluarkan daripada tindanan pada penghujungnya, walaupun tiada batang yang lebih pendek muncul secara semula jadi. Tanpa penanda itu, anda memerlukan fasa pembersihan selepas gelung untuk elemen tindanan yang masih tinggal.
def largest_rectangle(heights):
stack = [] # monotonic increasing: indices of bars
max_area = 0
heights = heights + [0] # sentinel: forces all bars to be popped
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()] # height of the rectangle
width = i if not stack else i - stack[-1] - 1 # left boundary
max_area = max(max_area, height * width)
stack.append(i)
return max_area
print(largest_rectangle([2, 1, 5, 6, 2, 3])) # 10
print(largest_rectangle([2, 4])) # 4
print(largest_rectangle([1, 1])) # 2
print(largest_rectangle([0, 9])) # 9
print(largest_rectangle([6, 7, 5, 2, 4, 5, 9, 3])) # 16Menjejak Algoritma Satu Laluan
Mari kita jejak [2, 1, 5, 6, 2, 3, 0] (dengan penanda) langkah demi langkah:
- i=0, tinggi=2: masukkan 0. Tindanan: [0]
- i=1, tinggi=1: pop 0 (tinggi=2, lebar=1, luas=2). Tindanan kosong, masukkan 1. Tindanan: [1]
- i=2, tinggi=5: 5>1, masukkan 2. Tindanan: [1,2]
- i=3, tinggi=6: 6>5, masukkan 3. Tindanan: [1,2,3]
- i=4, tinggi=2: pop 3 (tinggi=6,lebar=4-2-1=1,luas=6), pop 2 (tinggi=5,lebar=4-1-1=2,luas=10★), 2>1 berhenti. Masukkan 4. Tindanan: [1,4]
- i=5, tinggi=3: 3>2, masukkan 5. Tindanan: [1,4,5]
- i=6, penanda tinggi=0: lakukan pop pada semua elemen, sambil mengira luas...
def largest_rectangle_trace(heights):
stack = []
max_area = 0
hs = heights + [0]
for i, h in enumerate(hs):
while stack and hs[stack[-1]] > h:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
area = hs[top] * w
print(f' Pop bar {top} (h={hs[top]}): width={w}, area={area}', end='')
if area > max_area:
max_area = area
print(' *** NEW MAX ***', end='')
print()
print(f'i={i} h={h}: push {i}, stack={[hs[s] for s in stack + [i]]}')
stack.append(i)
print(f'Max area: {max_area}')
return max_area
largest_rectangle_trace([2, 1, 5, 6, 2, 3])Pengiraan Lebar: Mengapa i - stack[-1] - 1?
Apabila kita melakukan pop pada batang j daripada tindanan, kita tahu: sempadan kanan segi empat tepat bagi j ialah i (batang pertama di sebelah kanan yang lebih pendek daripada j). Sempadan kiri ialah batang yang berada tepat di bawah j dalam tindanan selepas pop — namakannya k. Oleh itu, lebarnya ialah i - k - 1 (batang dari k+1 hingga i-1 secara inklusif).
Jika tindanan kosong selepas pop, segi empat tepat bagi j memanjang hingga ke tepi kiri (indeks 0). Lebarnya hanyalah i (indeks 0 hingga i-1, yang semuanya sekurang-kurangnya setinggi ketinggian[j]). Ini ialah kes khas width = i if not stack else i - stack[-1] - 1.
# Illustrating left/right boundary logic
heights = [1, 3, 5, 2]
# After processing with stack:
# When we pop bar 2 (h=5) at i=3 (h=2):
# stack after pop = [0, 1] => left boundary = 1+1=2, right=3-1=2 => width=1
# When we pop bar 1 (h=3) at i=3 (h=2):
# stack after pop = [0] => left boundary = 0+1=1, right=3-1=2 => width=2
# etc.
def compute_boundaries(heights):
hs = heights + [0]
stack = []
for i, h in enumerate(hs):
while stack and hs[stack[-1]] > h:
top = stack.pop()
if stack:
left = stack[-1] + 1
width = i - stack[-1] - 1
else:
left = 0
width = i
print(f'Bar {top} (h={hs[top]}): extends from {left} to {i-1}, width={width}')
stack.append(i)
compute_boundaries([2, 1, 5, 6, 2, 3])Segi Empat Tepat Maksimum dalam Matriks Binari
Segi Empat Tepat Maksimum (LeetCode 85) mengembangkan masalah histogram kepada matriks binari 2D. Bagi setiap baris, hitung ketinggian 1 berturutan di atas setiap sel. Ini menghasilkan histogram untuk baris tersebut. Gunakan algoritma segi empat tepat terbesar dalam histogram pada histogram setiap baris. Nilai maksimum keseluruhan bagi semua baris ialah jawapannya.
Ini mengurangkan masalah 2D kepada n masalah histogram 1D yang diulang. Kerumitan masa ialah O(m × n) untuk matriks dengan m baris dan n lajur — satu laluan histogram bagi setiap baris, dengan setiap laluan mengambil O(n).
def maximal_rectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
max_area = 0
def hist_max_area(h):
stack, area = [], 0
for i, hh in enumerate(h + [0]):
while stack and h[stack[-1]] > hh:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
area = max(area, h[top] * w)
stack.append(i)
return area
for row in matrix:
for j in range(n):
heights[j] = heights[j] + 1 if row[j] == '1' else 0
max_area = max(max_area, hist_max_area(heights[:]))
return max_area
matrix = [['1','0','1','0','0'],
['1','0','1','1','1'],
['1','1','1','1','1'],
['1','0','0','1','0']]
print(maximal_rectangle(matrix)) # 6Kes Tepi dalam Masalah Histogram
Kes tepi penting yang perlu dikendalikan:
- Semua ketinggian sama: seluruh tatasusunan membentuk satu segi empat tepat; jawapan = n × ketinggian
- Menaik secara monotonik: tiada pop berlaku sehingga penanda; luas batang terakhir ialah maksimum
- Satu batang: jawapan = ketinggian[0]
- Batang dengan ketinggian 0: batang ini bertindak sebagai penanda semula jadi yang membahagikan histogram kepada segmen bebas
Penanda (menambahkan 0) pada penghujung mengendalikan kes menaik secara monotonik dengan memaksa semua batang yang masih tinggal dikeluarkan pada penghujungnya. Tanpa penanda itu, anda memerlukan gelung pembersihan berasingan selepas lelaran utama.
def largest_rectangle(heights):
stack = []
max_area = 0
heights = heights + [0]
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
max_area = max(max_area, heights[top] * w)
stack.append(i)
return max_area
# Edge cases
print(largest_rectangle([5, 5, 5, 5])) # 20 (all same)
print(largest_rectangle([1, 2, 3, 4, 5])) # 9 (increasing: 3*3)
print(largest_rectangle([5, 4, 3, 2, 1])) # 9 (decreasing: 3*3)
print(largest_rectangle([5])) # 5 (single bar)
print(largest_rectangle([0, 0, 0])) # 0 (all zero)
print(largest_rectangle([3, 0, 3])) # 3 (zero splits)Alternatif Bahagi dan Takluk
Masalah histogram juga boleh diselesaikan dengan bahagi dan takluk: bahagikan pada batang dengan ketinggian minimum, selesaikan setiap separuh secara rekursif dan bandingkan dengan segi empat tepat yang merentangi lebar penuh menggunakan ketinggian minimum. Ini memberikan O(n log n) secara purata tetapi O(n²) dalam kes terburuk bagi data masukan yang tersusun.
Pendekatan tindanan monotonik sememangnya lebih baik pada O(n) dalam kes terburuk. Walau bagaimanapun, memahami pendekatan bahagi dan takluk memperdalam intuisi terhadap masalah dan menerangkan mengapa batang dengan ketinggian minimum dalam mana-mana segmen sentiasa menjadi faktor pembatas bagi segi empat tepat berlebar penuh.
def largest_rectangle_dc(heights, lo=0, hi=None):
if hi is None:
hi = len(heights) - 1
if lo > hi:
return 0
# Find the index of the minimum height in [lo, hi]
min_idx = lo
for i in range(lo, hi + 1):
if heights[i] < heights[min_idx]:
min_idx = i
# Three options:
# 1. Max rect entirely in left half
# 2. Max rect entirely in right half
# 3. Max rect spanning entire [lo, hi] with height = min
full_width_area = heights[min_idx] * (hi - lo + 1)
left_area = largest_rectangle_dc(heights, lo, min_idx - 1)
right_area = largest_rectangle_dc(heights, min_idx + 1, hi)
return max(full_width_area, left_area, right_area)
print(largest_rectangle_dc([2, 1, 5, 6, 2, 3])) # 10Corak Histogram: Bilangan Subtatasusunan
Masalah berkaitan yang menggunakan teknik tindanan yang sama: hitung bilangan subtatasusunan dalam histogram yang elemen minimumnya sama dengan sasaran tertentu. Jawapannya diperoleh dengan menghitung PSE dan NSE bagi setiap batang, kemudian menggunakan formula (i - pse[i]) × (nse[i] - i) yang menghitung subhistogram yang batang i-nya ialah minimum.
Teknik 'bilangan kiri × bilangan kanan' ini muncul dalam beberapa masalah LeetCode: sum of subarray minimums (907), pengiraan subrentetan dengan semua aksara unik dan masalah teknik sumbangan. Tindanan monotonik menghitung PSE dan NSE dalam O(n), sekali gus membolehkan sumbangan setiap elemen dihitung dalam O(1).
def sum_of_subarray_minimums(arr):
n = len(arr)
pse = [-1] * n # previous strictly smaller element
nse = [n] * n # next smaller or equal element
stack = []
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
pse[i] = stack[-1] if stack else -1
stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
nse[i] = stack[-1] if stack else n
stack.append(i)
MOD = 10**9 + 7
total = 0
for i in range(n):
left_count = i - pse[i] # subarrays where i is leftmost min
right_count = nse[i] - i # subarrays where i is the min
total += arr[i] * left_count * right_count
return total % MOD
print(sum_of_subarray_minimums([3, 1, 2, 4])) # 17
print(sum_of_subarray_minimums([11, 81, 94, 43, 3])) # 444Petua Praktikal Temu Duga
Apabila anda melihat masalah histogram dalam temu duga, ikuti senarai semak ini:
- Jelaskan: bolehkah ketinggian bernilai 0? Apakah hasilnya — luas, indeks atau bilangan?
- Mulakan dengan pendekatan daya kasar dan nyatakan kerumitan O(n²) atau O(n³)
- Sebutkan bahawa sumbangan setiap batang bergantung pada sejauh mana batang itu memanjang ke kiri dan kanan hingga batang lebih pendek terdekat
- Perkenalkan PSE/NSE → tindanan monotonik → penyelesaian O(n)
- Gunakan helah penanda (append 0) untuk memudahkan kod
- Jejak contoh kecil pada papan putih
Soalan susulan yang biasa: lanjutkan kepada 2D (segi empat tepat maksimum). Tunjukkan bahawa anda boleh mengurangkannya kepada n masalah histogram, setiap satunya O(n), untuk jumlah keseluruhan O(m×n).
# Final clean solution for interview
def largest_rectangle_in_histogram(heights):
stack = []
max_area = 0
for i, h in enumerate(heights + [0]): # sentinel forces final pops
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
# Verify all test cases from earlier
test_cases = [
([2, 1, 5, 6, 2, 3], 10),
([6, 7, 5, 2, 4, 5, 9, 3], 16),
([1], 1),
([2, 0, 2], 2),
([], 0),
]
for heights, expected in test_cases:
if not heights:
result = 0
else:
result = largest_rectangle_in_histogram(heights)
status = 'PASS' if result == expected else 'FAIL'
print(f'{status}: {heights} => {result} (expected {expected})')Jumlah Julat Subtatasusunan dan Variasi Serupa
Teknik PSE/NSE boleh digeneralisasikan kepada beberapa masalah LeetCode. Jumlah Julat Subtatasusunan (2104) meminta jumlah (maksimum - minimum) merentas semua subtatasusunan. Nilai ini sama dengan (jumlah maksimum subtatasusunan) ditolak (jumlah minimum subtatasusunan), yang masing-masing dikira dengan tindanan monotonik dalam O(n). Bilangan Orang yang Kelihatan dalam Baris Gilir (1944) menggunakan tindanan menurun, yang setiap popnya mengira seorang yang kelihatan. Anda boleh mengenali kelompok masalah ini dengan menyedari frasa 'bagi setiap elemen, sejauh mana elemen itu boleh mendominasi?' — jawapannya sentiasa PSE/NSE dengan tindanan monotonik.
def sum_subarray_ranges(nums):
n = len(nums)
# Sum of subarray max - sum of subarray min
def contrib(arr, is_max):
# Count contribution of each element as max (or min)
n = len(arr)
left = [0]*n; right = [0]*n
stack = []
for i in range(n):
while stack and (arr[stack[-1]] < arr[i] if is_max else arr[stack[-1]] > arr[i]):
stack.pop()
left[i] = i - (stack[-1] if stack else -1)
stack.append(i)
stack = []
for i in range(n-1, -1, -1):
while stack and (arr[stack[-1]] <= arr[i] if is_max else arr[stack[-1]] >= arr[i]):
stack.pop()
right[i] = (stack[-1] if stack else n) - i
stack.append(i)
return sum(arr[i] * left[i] * right[i] for i in range(n))
return contrib(nums, True) - contrib(nums, False)
print(sum_subarray_ranges([1, 2, 3])) # 4
print(sum_subarray_ranges([1, 3, 3])) # 4
print(sum_subarray_ranges([4, -2, -3, 4, 1])) # 59Semakan Pantas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Ulang Kaji Pelajaran
Dalam pelajaran ini, anda telah mempelajari bahawa: bagi setiap batang, segi empat tepat terbesar yang mengandungi batang itu mempunyai sempadan yang ditentukan oleh batang lebih pendek terdekat pada setiap sisi (PSE dan NSE), tindanan menaik monotonik mengira semua sempadan PSE/NSE dalam satu laluan O(n) dengan menemui kedua-duanya apabila batang dikeluarkan, dan menambahkan penanda 0 memastikan semua batang dikeluarkan daripada tindanan, sekali gus memudahkan kod menjadi satu gelung sahaja. Seterusnya, kita akan menggunakan baris gilir dua hujung monotonik untuk menyelesaikan nilai maksimum tetingkap gelongsor dalam O(n).
Pelajari Python 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
- 30
- Pelajaran
- 120
Soalan Lazim
Adakah pelajaran “Segi Empat Terbesar dalam Histogram” percuma?
Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “Segi Empat Terbesar dalam Histogram”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Segi Empat Terbesar dalam Histogram”?
Gunakan tindanan monoton untuk menjejak sempadan kiri dan mengira luas maksimum segi empat yang muat dalam histogram dalam satu laluan. Anda berlatih DSA Interview Prep 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 DSA Interview Prep?
Tiada pengalaman terdahulu diperlukan. Pembelajaran DSA Interview Prep 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 2 daripada 4.
Berapa lamakah pelajaran “Segi Empat Terbesar dalam Histogram” 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 DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep 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
- Tindanan Monoton: Menaik berbanding Menurun
- Segi Empat Terbesar dalam Histogram
- Maksimum Tetingkap Gelongsor dengan Dek Monoton
- Memerangkap Air Hujan: Tindanan dan Dua Penuding