Leetcode 84 Largest Rectangle in Histogram

Soru

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Örnek 1

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Örnek 2

Input: heights = [2,4]
Output: 4

Çözüm

• Bir histogramda oluşturulabilecek en büyük dikdörtgenin alanını bulmanızı ister. Histogram, çubukların yüksekliklerini temsil eden bir tam sayı dizisiyle verilir ve her çubuğun genişliği 1 birimdir.
• Girdi: Histogramın yüksekliklerini temsil eden bir tam sayı dizisi heights.
• Çıktı: Histogram içinde oluşturulabilecek en büyük dikdörtgenin alanı.
• Bu problem genellikle bir yığın (stack) kullanılarak çözülür. Yığın, yükseklikleri ve çubukların indekslerini saklayarak, her bir çubuk için sol ve sağda kendisinden daha kısa olan ilk çubuğun konumunu bulmamızı sağlar. Bu bilgi, her çubuk için potansiyel olarak oluşturulabilecek en büyük dikdörtgenin alanını hesaplamak için kullanılabilir.
• Çalışma Mekanizması:
• Yığın İnitialize Edilmesi: Yığın boş başlar ve histogramın yükseklikleri döngüyle işlenir.
• Dikdörtgen Alanının Hesaplanması: Her adımda, mevcut çubuğun yüksekliği yığındaki son çubuktan daha düşükse, yığının en üstündeki çubuk çıkarılır ve bu çubuk için maksimum dikdörtgen alanı hesaplanır. Çıkarılan çubuk, yığında kalan sonraki çubuk ile mevcut çubuk arasında bir dikdörtgen oluşturur.
• Yeni Çubukların Eklenmesi: Her çubuk, kendisinden önce gelen ve kendisinden daha yüksek olan çubukların yığına eklenmesiyle işlenir.
• Sonlandırma: Histogramın sonuna eklenen sıfır sayesinde, tüm çubuklar için hesaplama tamamlanabilir.
• Maksimum Alanın Dönüşü: Hesaplanan maksimum dikdörtgen alanı döndürülür.

Code

class Solution:
    def largestRectangleArea(self, heights):
        stack = []
        max_area = 0
        heights.append(0)  # Histogramın sonuna bir sıfır ekleyerek sonlandırma kolaylaştırılır.

        for i in range(len(heights)):
            while stack and heights[stack[-1]] > heights[i]:
                h = heights[stack.pop()]
                w = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, h * w)
            stack.append(i)
        
        heights.pop()  # Eklenen sıfırı kaldır.
        return max_area


        

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(n), burada n çubuk sayısıdır. Her çubuk yığına en fazla bir kez eklenir ve bir kez çıkarılır.
• Space complexity (Alan Karmaşıklığı) : O(n), yığında en kötü durumda tüm çubuklar saklanabilir.