Largest Rectangle in Histogram
Histogram, aralarında boşluk olmadan yan yana duran ve her biri bir birim genişliğinde olan bir çubuk sırasıdır: heights[i], i çubuğunun yüksekliğidir. İçindeki bir dikdörtgen, yan yana bir dizi çubuğu kapsar ve bu dizideki en kısa çubuktan daha yüksek olamaz.
Böyle bir dikdörtgenin sahip olabileceği en büyük alanı döndürün.
Fonksiyon
- heightsinteger-array
- soldan sağa her çubuğun yüksekliği
- Döndürürinteger
- histograma sığan en büyük dikdörtgenin alanı
Kısıtlar
1 ≤ heights.length ≤ 2 × 1040 ≤ heights[i] ≤ 105- Her çubuk bir birim genişliğindedir; bu nedenle
iilejarasındaki çubukların üzerindeki bir dikdörtgenin genişliğij-i+1birimdir.
Örnekler
- Girdi
- heights = [2, 5, 6, 3, 4, 1]
- Çıktı
- 12
- Açıklama
- 5, 6, 3 ve 4 uzunluğundaki dört çubuğun tümü en az 3 yüksekliğindedir; bu nedenle yüksekliği 3 olan bir dikdörtgen bunların üzerinden geçer: 3 × 4 = 12. En uzun iki çubuk olan 5 ve 6 ise yalnızca 5 × 2 = 10 verir.
- Girdi
- heights = [1, 8, 1, 1]
- Çıktı
- 8
- Açıklama
- Yalnızca 8'lik çubuk 8 × 1 = 8 eder. Daha geniş herhangi bir dikdörtgen 1'lik bir çubuk içerir, dolayısıyla en fazla 1 × 4 = 4 eder.
- Girdi
- heights = [3, 3, 3, 3]
- Çıktı
- 12
- Açıklama
- Dört çubuğun da yüksekliği 3 olduğundan, histogramın tamamı tek bir dikdörtgendir: 3 × 4 = 12.
Gönderirken +17 gizli test
Ek soru
Her çubuğun, ikinci bir dizide verilen kendi genişliği olduğunu varsayalım. Tek geçişli yığın çözümünde neler değişir?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
En büyük dikdörtgen, altındaki çubuklardan en az birinin üst kenarına değmelidir: değmeseydi, onu daha uzun yapabilirdiniz. Bu yüzden yüksekliği belirleyen çubuk olarak her çubuğu deneyin. Tam olarak bu yükseklikteki bir dikdörtgen ne kadar geniş olabilir?
içubuğu kadar yüksek bir dikdörtgen, her iki tarafta da kendisinden kesin olarak daha kısa bir çubukla karşılaşana kadar sola ve sağa doğru genişler. Her çubuğun her iki tarafındaki en yakın daha kısa çubuğu biliyorsan, her çubuk bir alan adayı verir ve bunlardan yalnızcantane vardır.Yükseklikleri alttan üste doğru artan indekslerden oluşan bir yığın tut. Üstteki çubuktan daha yüksek olmayan bir çubuk geldiğinde, üstteki çubuk artık daha sağa ulaşamaz: Onu yığından çıkar; dikdörtgeni, yığının yeni üstü ile mevcut çubuk arasındaki çubukları kapsar. Sondan sonra gelen 0 yüksekliğindeki bir çubuk, geriye ne kaldıysa çıkarır.
Çözüm
Bir dikdörtgen herhangi bir çubukta başlayıp bitebilir ve yüksekliği kapsadığı en alçak çubuğa bağlıdır; bu nedenle her çubuk aralığını denemek yaklaşık n²/2 adım gerektirir. Çözüm, soruyu tersine çevirmektir: en iyi dikdörtgen tam olarak çubuklarından birinin yüksekliğindedir; bu yüzden her çubuğun yalnızca daha kısa bir çubuk onu durdurana kadar ne kadar genişleyebileceğini bilmesi gerekir. Monoton bir yığın, önce iki geçişte, ardından tek geçişte her çubuk için bu durma noktalarını bulur.
Her çalıştırmada çalışan minimum değeri dene
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Bir dikdörtgen, start ile end arasındaki bitişik çubuklardan oluşan bir aralığı kaplar ve yüksekliği bu aralıktaki en alçak çubukla sınırlıdır. Bu yüzden her aralığı deneyin. start değerini sabitleyin, ardından end değerini her seferinde bir çubuk artırın ve şimdiye kadar görülen en düşük yüksekliği takip edin. Bu aralıktaki en iyi dikdörtgenin alanı lowest × (end-start+1) olur.
[2, 5, 6, 3, 4, 1] dizisinde 5'ten başlayın. Aralıklar 5 × 1 = 5, ardından 6 eklendiğinde 5 × 2 = 10, 3 aralığa katıldığında 3 × 3 = 9, 4 eklendiğinde 3 × 4 = 12 ve 1 eklendiğinde 1 × 5 = 5 sonuçlarını verir. Cevap 12'dir. Aralık büyürken lowest değerini güncellemek her adımı O(1) yapar; böylece minimumu bulmak için bir aralığı yeniden taramanız gerekmez.
Bu yöntem doğrudur; çünkü her dikdörtgen bir aralığın üzerinde yer alır ve sabit bir aralık için sığabilecek en yüksek dikdörtgen, tam olarak en alçak çubuk kadar yüksektir. Yavaştır; çünkü n(n+1)/2 aralık vardır: 2 × 10^4 çubuk için yaklaşık 2 × 10^8 aralık ve bu sayı yüksekliklere hiçbir şekilde bağlı değildir. Bu aralıkların çoğu, bitişlerine ulaşmadan çok önce alçak bir çubuk tarafından kısaltılır; ancak kaba kuvvet yöntemi yine de onları genişletmeye devam eder.
Algoritma
bestdeğerini 0 olarak ayarla.- Her
startiçinlowestdeğeriniheights[start]olarak ayarla. startdeğerinden son çubuğa kadar herendiçin, çubuk daha kısaysalowestdeğeriniheights[end]olarak düşür.bestdeğerinilowest × (end-start+1)ile güncelle.bestdeğerini döndür.
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 bestHer iki taraftaki en yakın daha kısa çubuk
Sezgi
Aramayı tersine çevirin. En iyi dikdörtgende, altındaki çubuklardan en az biri dikdörtgenle tam olarak aynı yüksekliktedir; aksi hâlde dikdörtgeni yükseltebilirdiniz. Dolayısıyla yanıt, her i çubuğu için, tam olarak heights[i] yüksekliğinde ve olabildiğince geniş olan dikdörtgenlerin en büyüğüdür. Dikdörtgen, her iki tarafta da kendisinden kesin olarak daha kısa bir çubukla karşılaşana kadar genişler. Bunların indislerine left[i] ve right[i] diyelim; yoksa -1 ve n kullanalım. Dikdörtgen, bu çubukların kesinlikle arasında kalan çubukları kapsar: genişlik right[i]-left[i]-1. Böylece n²/2 yerine n adayımız olur.
Her çubuk için left[i] değerini bulmak üzere, yükseklikleri yığının altından üstüne doğru kesin olarak artan indislerden oluşan bir yığınla soldan sağa ilerleyin. i çubuğu geldiğinde, çubuğu heights[i] kadar uzun veya daha uzun olan tüm indisleri yığından çıkarın. Bu çubuklar, i için veya ondan sonraki herhangi bir çubuk için en yakındaki daha kısa çubuk olamaz; çünkü i daha yakındır ve daha uzun değildir. Üstte geriye kalan, soldaki en yakındaki daha kısa çubuktur. Ardından i değerini yığına ekleyin. Sağdan sola yapılan aynı geçiş right[i] değerini verir.
[2, 5, 6, 3, 4, 1] için geçişler left = [-1, 0, 1, 0, 3, -1] ve right = [5, 3, 3, 5, 5, 6] değerlerini verir. 3. indisteki 3 yüksekliğindeki çubuk, 0. indisteki 2 ve 5. indisteki 1 tarafından durdurulur; dolayısıyla dikdörtgeni 3 × (5-0-1) = 12 olur. 6 yüksekliğindeki çubuk komşuları tarafından sıkıştırılır ve yalnızca 6 × 1 değerini verir.
Her indis her geçişte bir kez yığına eklenir ve en fazla bir kez çıkarılır; bu nedenle bir çubuk birçok çubuğu çıkarabilse bile iki geçişin toplamı O(n) olur. Bunun karşılığında iki ek dizi gerekir.
Algoritma
- Boş bir yığınla soldan sağa ilerle. Her
iiçin, en üstteki çubukheights[i]kadar veya daha uzunsa yığından çıkar; yığın boşsaleft[i]değerini en üstteki öğe, yoksa -1 olarak ayarla;ideğerini yığına ekle. right[i]değerini doldurmak için aynı şekilde sağdan sola ilerle; yığın boşsankullan.- Her
iiçinheights[i] × (right[i]-left[i]-1)değerini hesapla. - Bu alanların en büyüğünü döndür.
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 bestMonotonik yığınla tek geçiş
Sezgi
Soldan sağa geçiş, sağdaki tüm sınırları zaten görür; ancak onları atar. i çubuğu t çubuğunu yığından çıkardığında, heights[i] değeri heights[t] değerinden büyük değildir; dolayısıyla i, t dikdörtgeninin sağda sona erdiği yerdir. Yığındaki t öğesinin hemen altında kalan indeks ise dikdörtgenin solda sona erdiği yerdir. Öyleyse dikdörtgenin alanını, çubuğu yığından çıkardığın anda hesapla: heights[t] × (i - below - 1); burada below yığının yeni tepesidir veya yığın artık boşsa -1'dir.
Değişmez: yığındaki yükseklikler alttan üste doğru kesin olarak artar ve her öğenin altındaki indeks, solundaki kendisinden daha kısa olan en yakın çubuğun indeksidir. İki çubuk arasındaki her çubuk, ya söz konusu öğenin kendisi ya da öğenin daha sonra yığından çıkardığı bir çubuk tarafından bu sırada yığından çıkarılmıştır; dolayısıyla bunların hiçbiri söz konusu öğeden daha kısa değildir. Hiç yığından çıkarılmayan çubuklar dizinin sonuna kadar uzanır; bu nedenle son çubuğu işledikten sonra bir kez daha yüksekliği 0 olan bir çubuk işlersin. Bu çubuk her şeyden kısadır ve yığını boşaltır.
[2, 5, 6, 3, 4, 1] dizisini adım adım inceleyelim. 2, 5 ve 6'yı ekle: yığında [0, 1, 2] indeksleri bulunur. 3. indeksteki 3, önce 6'yı yığından çıkarır (alan 6 × (3-1-1) = 6), ardından 5'i çıkarır (alan 5 × (3-0-1) = 10); sonra 2'de durur ve yığına eklenir. 4'ü de ekle. 5. indeksteki 1, önce 4'ü çıkarır (alan 4), ardından dikdörtgeni 1. indeksten 4. indekse kadar uzanan 3'ü çıkarır: 3 × (5-0-1) = 12. 2'yi de çıkarır (2 × 5 = 10; yığın boş olduğundan genişlik 5'tir). Sondaki 0, 1'i yığından çıkarır (1 × 6 = 6). En büyük alan 12'dir.
>= koşulunda yığından çıkarma, eşit yükseklikteki bir çubuğun başka bir çubuğu erkenden durdurmasına yol açabilir. Bu güvenlidir: eşit yükseklikteki çubuk onun yığındaki yerini alır ve aynı sol sınırı devralır; daha sonra yığından çıkarıldığında dikdörtgeni eşit yükseklikteki çubukların tüm dizisini kapsar. [3, 3, 3, 3] dizisinde ilk üç 3 sırasıyla 1, 2 ve 3 genişliklerini kaydeder; sonuncusu ise sondaki 0 tarafından 4 genişlikle yığından çıkarılır ve 12 alanını verir.
Algoritma
- Boş bir indis yığını ve
best = 0ile başla. - 0'dan
n'ye kadariiçin geçerli yükseklikheights[i]olsun;i = nolduğunda ise 0 olsun. - Yığının en üstündeki çubuk geçerli yükseklikten büyük veya ona eşit olduğu sürece, onu
tolarak çıkar; genişliki - below - 1olur; buradabelow, yeni en üstteki indis veya -1'dir.bestdeğeriniheights[t] × widthile güncelle. i'yi yığına ekle.bestdeğerini döndür.
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
Tuzaklar ve uç durumlar
Yığın döngüsü kısadır ve hataların neredeyse tamamı genişlikte ya da sonda yığında kalan çubuklardadır.
- Yığında kalan çubukları unutmamak.
[1, 2, 3, 4, 5]gibi yükselen bir histogramda döngü içinde hiçbir şey yığından çıkarılmaz ve yüksekliği 0 olan kapanış çubuğu olmadan 9 yerine 0 döndürürsün. - Genişliği, yığından çıkarılan çubuğun kendi indeksinden ölçmek. Dikdörtgeni, yığındaki altındaki çubuğun hemen sonrasından başlar; çubuğun kendisinden değil:
[2, 5, 6, 3, 4, 1]dizisinde, 3. indeksteki 3, 1 ile 4. indeksler arasını kapsar.i - tkullanmak 4 yerine 2 verir. - Çıkarma işleminden sonra yığın boşsa yanlış genişliği kullanmak. Çıkarılan çubuk şu ana kadarki en alçak çubuktur; dolayısıyla dikdörtgeni 0. indekse kadar uzanır ve genişlik
iolur.[2, 1, 2]dizisinde 1, alanı 3 olan üç çubuğun tamamını kapsar. - İki geçişli sürümde her iki tarafta da eşit çubuklarda durmak. Böylece
[3, 3, 3, 3]dizisinde her çubuk 1 genişlik görür ve 12 yerine 3 döndürürsün. Sınırların kesin olarak daha kısa çubuklar olması için>=koşulunda yığından çıkar. - En uzun çubuğun ya da en geniş aralığın kazanacağını varsaymak.
[2, 5, 6, 3, 4, 1]dizisinde ne 6 yüksekliği ne de 6 çubuğun tamamını kapsayan genişlik yanıtı verir; orta genişlikteki orta yükseklik verir. - Taşma. Burada alan
10^5 × 2 × 10^4 = 2 × 10^9değerine ulaşır; bu da işaretli 32 bitlik bir tam sayıya sığar. Daha büyük sınırlarla çarpımı 64 bitlik türde yap.
Sıkça sorulan sorular4
Histogramdaki En Büyük Dikdörtgen algoritmasının zaman karmaşıklığı nedir?
Monotonik yığın çözümü O(n) zamanda çalışır ve O(n) ek alan kullanır. Her indeks bir kez yığına eklenir ve bir kez çıkarılır; her çıkarma sabit miktarda iş gerektirir. Çubukların her aralığını denemek O(n²) zaman alır; 2 × 10^4 çubuk için yaklaşık 2 × 10^8 adımdır.
Bir çubuğun dikdörtgeni neden açılırken ölçülür?
Bir çubuk, sağında kendisinden daha uzun olmayan ilk çubuk tarafından çıkarılır; dolayısıyla dikdörtgeni sağda orada biter. Yığının altında bulunan indeks, solundaki en yakın daha kısa çubuğu gösterir; dolayısıyla çubuk solda orada biter. Çubuk çıkarıldığı anda her iki uç da bilinir ve alan height × (i - below - 1) olur.
Histogramdaki En Büyük Dikdörtgen, böl ve yönet yöntemiyle çözülebilir mi?
Evet. Tüm aralıktaki en alçak çubuk ya en iyi dikdörtgenin altında kalır; bu durumda dikdörtgenin alanı lowest × width olur ya da aralığı, ayrı ayrı çözeceğiniz sol ve sağ kısımlara böler. Minimumu bulmak için doğrusal tarama kullanıldığında, rastgele girdilerde karmaşıklık O(n log n), sıralı girdilerde ise O(n²) olur; aralık minimumları için segment ağacı kullanmak karmaşıklığı her zaman O(n log n) yapar. Yığın daha basit ve hızlıdır.
Largest Rectangle in Histogram, 0/1 ızgarasındaki maksimum dikdörtgen için nasıl kullanılır?
Izgarayı satır satır dolaşın ve her sütun için, geçerli satırda sona eren ardışık 1'lerin sayısını tutun; 0 bu sayıyı sıfırlar. Her satırın sayıları bir histogram oluşturur ve o satırda sona eren en büyük 1 dikdörtgeni, bu histogramdaki en büyük dikdörtgendir. Yığını her satırda bir kez çalıştırmak, ızgarayı O(rows × cols) zamanda çözer.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def largestRectangleArea(heights):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
heights = [2, 5, 6, 3, 4, 1]
Beklenen
12