Largest Rectangle in Histogram
Histogram adalah deretan batang yang berdiri berdampingan tanpa celah, masing-masing lebarnya satu unit: heights[i] adalah tinggi batang i. Sebuah persegi panjang di dalamnya mencakup sederetan batang yang bersebelahan dan tingginya tidak boleh melebihi batang terpendek dalam deretan tersebut.
Kembalikan luas terbesar yang dapat dimiliki persegi panjang seperti itu.
Fungsi
- heightsinteger-array
- tinggi setiap batang, dari kiri ke kanan
- Mengembalikaninteger
- luas persegi panjang terbesar yang muat di dalam histogram
Batasan
1 ≤ heights.length ≤ 2 × 1040 ≤ heights[i] ≤ 105- Setiap batang lebarnya satu unit, jadi persegi panjang yang membentang dari batang
ihinggajlebarnyaj-i+1unit.
Contoh
- Input
- heights = [2, 5, 6, 3, 4, 1]
- Output
- 12
- Penjelasan
- Batang 5, 6, 3, dan 4 semuanya memiliki tinggi setidaknya 3, jadi persegi panjang dengan tinggi 3 membentang di sepanjang batang-batang itu: 3 × 4 = 12. Dua batang tertinggi hanya menghasilkan 5 × 2 = 10.
- Input
- heights = [1, 8, 1, 1]
- Output
- 8
- Penjelasan
- Batang berukuran 8 saja menghasilkan 8 × 1 = 8. Persegi panjang yang lebih lebar mencakup batang berukuran 1, jadi ukurannya paling besar 1 × 4 = 4.
- Input
- heights = [3, 3, 3, 3]
- Output
- 12
- Penjelasan
- Keempat batang tingginya 3, jadi seluruh histogram berbentuk satu persegi panjang: 3 × 4 = 12.
Pertanyaan lanjutan
Misalkan setiap batang memiliki lebarnya sendiri, yang diberikan dalam array kedua. Apa yang berubah pada solusi tumpukan satu lintasan?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Persegi panjang terbesar menyentuh bagian atas setidaknya satu batang di bawahnya: jika tidak, kamu bisa membuatnya lebih tinggi. Jadi, coba setiap batang sebagai batang yang menentukan tinggi. Seberapa lebar persegi panjang dengan tinggi tepat seperti itu?
Persegi panjang setinggi batang
imeluas ke kiri dan kanan hingga bertemu batang yang lebih pendek secara ketat di setiap sisinya. Jika kamu mengetahui batang terdekat yang lebih pendek di setiap sisi dari setiap batang, setiap batang memberikan satu kandidat luas, dan jumlahnya hanyan.Simpan tumpukan indeks dengan tinggi yang meningkat dari bawah ke atas. Saat sebuah batang tiba yang tingginya tidak lebih besar dari batang teratas, batang teratas tidak dapat menjangkau lebih jauh ke kanan: keluarkan batang itu, lalu perseginya mencakup batang-batang yang berada tepat di antara indeks teratas yang baru dan batang saat ini. Batang dengan tinggi 0 setelah akhir mengeluarkan apa pun yang tersisa.
Solusi
Mencoba setiap rentang batang membutuhkan sekitar n²/2 langkah. Balik cara berpikirnya: persegi panjang terbaik tingginya persis sama dengan salah satu batang, jadi setiap batang hanya perlu mengetahui seberapa jauh rentangnya sebelum terhenti oleh batang yang lebih pendek. Stack monoton menemukan titik-titik tersebut dalam O(n).
Coba setiap run dengan nilai minimum yang terus diperbarui
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Tetapkan start, naikkan end satu batang setiap kali, dan pertahankan tinggi terendah yang ditemukan sejauh ini. Persegi panjang terbaik pada rentang itu memiliki luas lowest × (end-start+1). Mulai dari angka 5 di [2, 5, 6, 3, 4, 1], rentang-rentangnya menghasilkan 5, 10, 9, 12, dan 5.
Algoritma ini benar karena setiap persegi panjang berada di atas suatu rentang dan tingginya tidak bisa melebihi batang terendah pada rentang itu. Algoritma ini lambat karena ada n(n+1)/2 rentang: sekitar 2 × 10^8 untuk 2 × 10^4 batang.
Algoritma
- Atur
bestke 0. - Untuk setiap
start, aturlowestkeheights[start]. - Untuk setiap
enddaristarthingga batang terakhir, turunkan nilailowestkeheights[end]jika batang tersebut lebih pendek. - Perbarui
bestdenganlowest × (end-start+1). - Kembalikan
best.
def largestRectangleArea(heights):
n = len(heights)
best = 0
for start in range(n):
lowest = heights[start]
for end in range(start, n):
# The rectangle over start..end is as tall as the lowest bar in it.
lowest = min(lowest, heights[end])
best = max(best, lowest * (end - start + 1))
return bestBatang terdekat yang lebih pendek di setiap sisi
Intuisi
Persegi panjang terbaik mencapai puncak setidaknya satu batang di bawahnya, jika tidak, kamu bisa menaikkannya. Jadi, untuk setiap batang i, ambil persegi panjang dengan tinggi tepat heights[i] yang membentang hingga batang yang lebih pendek secara ketat di setiap sisi, pada left[i] dan right[i] (-1 dan n jika tidak ada). Lebarnya adalah right[i]-left[i]-1.
Untuk menemukan left[i], telusuri dari kiri ke kanan menggunakan stack indeks yang tingginya meningkat. Batang i mengeluarkan setiap batang yang tingginya setidaknya sama dengan tinggi batang itu sendiri dari stack: tidak satu pun dari batang tersebut bisa menjadi batang terdekat yang lebih pendek bagi i atau batang mana pun setelahnya, karena i lebih dekat dan tidak lebih tinggi. Elemen teratas kemudian menjadi left[i]. Penelusuran dari kanan ke kiri menghasilkan right[i].
Setiap indeks dimasukkan dan dikeluarkan dari stack paling banyak satu kali per penelusuran, sehingga waktunya adalah O(n).
Algoritma
- Telusuri dari kiri ke kanan dengan tumpukan. Untuk setiap
i, keluarkan elemen dari tumpukan selama batang teratas setidaknya setinggiheights[i]; tetapkanleft[i]ke elemen teratas, atau -1 jika tumpukan kosong; lalu masukkani. - Telusuri dari kanan ke kiri dengan cara yang sama untuk
right[i], gunakannjika tumpukan kosong. - Kembalikan nilai terbesar dari
heights[i] × (right[i]-left[i]-1).
def largestRectangleArea(heights):
n = len(heights)
left = [-1] * n # index of the nearest shorter bar on the left, or -1
right = [n] * n # index of the nearest shorter bar on the right, or n
stack = [] # indices whose heights rise strictly from bottom to top
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if stack:
left[i] = stack[-1]
stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if stack:
right[i] = stack[-1]
stack.append(i)
best = 0
for i in range(n):
# Bar i is the lowest bar of everything strictly between left[i] and right[i].
best = max(best, heights[i] * (right[i] - left[i] - 1))
return bestSatu kali lintasan dengan stack monotonik
Intuisi
Pemindaian dari kiri ke kanan sudah menemukan setiap batas kanan, lalu membuangnya. Saat batang i mengeluarkan batang t dari tumpukan, batang i tidak lebih tinggi, jadi persegi panjang t berhenti di sana. Di sebelah kiri, persegi panjang itu berhenti di below, indeks yang sekarang berada di bawah t pada tumpukan, atau -1 jika tumpukan kosong. Ukur saat batang dikeluarkan: heights[t] × (i - below - 1).
Batas kiri itu benar karena setiap batang di antara sebuah entri dan batang di bawahnya dikeluarkan oleh entri tersebut, secara langsung atau melalui rangkaian, jadi tidak ada yang lebih pendek daripada entri itu. Batang penutup dengan tinggi 0 mengeluarkan semua yang tersisa. Pada contoh pertama, batang 1 di indeks 5 mengeluarkan batang 3 di indeks 3, dengan indeks 0 di bawahnya: 3 × 4 = 12.
Mengeluarkan batang yang tingginya sama lebih awal tetap aman: batang berikutnya mewarisi batas kirinya dan mengukur rentang penuh.
Algoritma
- Mulai dengan stack kosong dan
best = 0. - Untuk
idari 0 hinggan, ambil tinggiheights[i], atau 0 saati = n. - Selama batang teratas setidaknya setinggi itu, keluarkan sebagai
tdan perbaruibestdenganheights[t] × (i - below - 1), denganbelowsebagai elemen teratas yang baru atau -1. - Masukkan
i. - Kembalikan
best.
def largestRectangleArea(heights):
n = len(heights)
stack = [] # indices whose heights rise strictly from bottom to top
best = 0
for i in range(n + 1):
current = heights[i] if i < n else 0 # a bar of 0 past the end empties the stack
while stack and heights[stack[-1]] >= current:
# Bar i stops the popped bar on the right; the bar below it stops it on the left.
height = heights[stack.pop()]
left = stack[-1] if stack else -1
best = max(best, height * (i - left - 1))
stack.append(i)
return best
Jebakan dan kasus tepi
- Lupa memproses batang yang masih ada di tumpukan. Pada
[1, 2, 3, 4, 5], tidak ada yang dikeluarkan dari tumpukan di dalam perulangan. Tanpa 0 penutup, kamu mengembalikan 0, bukan 9. - Mengukur lebar dari indeks batang yang dikeluarkan dari tumpukan. Pada contoh pertama, batang bernilai 3 di indeks 3 membentang dari indeks 1 hingga 4.
i - tmenghasilkan 2, bukan 4. - Menghitung lebar dengan cara yang salah saat tumpukan kosong setelah sebuah batang dikeluarkan. Lebarnya adalah
i: pada[2, 1, 2], batang bernilai 1 membentang sepanjang ketiga batang, dengan luas 3. - Hanya mengeluarkan batang dari tumpukan saat memakai
>dalam versi dua lintasan. Pada[3, 3, 3, 3], setiap batang akan mendapatkan lebar 1, dan kamu mengembalikan 3, bukan 12.
Pertanyaan yang sering diajukan3
Apa kompleksitas waktu dari Largest Rectangle in Histogram?
Solusi stack monoton berjalan dalam waktu O(n) dan menggunakan ruang tambahan O(n): setiap indeks didorong sekali dan dikeluarkan sekali. Mencoba setiap rentang batang membutuhkan waktu O(n²).
Apakah Largest Rectangle in Histogram dapat diselesaikan dengan pendekatan bagi dan taklukkan?
Ya. Batang terendah dalam suatu rentang berada di bawah persegi panjang terbaik, yang luasnya kemudian lowest × width, atau membagi rentang menjadi dua bagian yang kamu selesaikan secara terpisah. Memindai nilai minimum membuat kompleksitasnya O(n log n) untuk input acak dan O(n²) untuk input terurut; segment tree membuat kompleksitasnya selalu O(n log n).
Bagaimana Largest Rectangle in Histogram digunakan untuk mencari persegi panjang terbesar dalam grid 0/1?
Telusuri baris demi baris dan hitung, untuk setiap kolom, jumlah angka 1 berturut-turut hingga baris saat ini; angka 0 mereset hitungan. Hitungan setiap baris membentuk histogram, dan persegi panjang terbesarnya adalah persegi panjang terbesar yang terdiri dari angka 1 dan berakhir pada baris tersebut: waktu total O(rows × cols).
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def largestRectangleArea(heights):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
heights = [2, 5, 6, 3, 4, 1]
Output yang diharapkan
12