Largest Rectangle in Histogram ใน Python

กำหนดอาร์เรย์จำนวนเต็มแทนความสูงของ histogram (แต่ละแท็บกว้าง 1) ต้องหาพื้นที่สี่เหลี่ยมผืนผ้ามากที่สุดที่ใส่ใน histogram ได้

ขั้นตอนการแก้ปัญหา (Monotonic Stack)

• ใช้ stack เก็บ index ของแท็บที่ความสูงเพิ่มขึ้น
• วน i จาก 0 ถึง n-1: ถ้า stack ว่างหรือ height[stack[-1]] ≤ height[i] → push i, i++
• ถ้า height[stack[-1]] > height[i]: pop x = stack.pop(), คำนวณพื้นที่ = height[x] * (i - stack[-1] - 1) (ถ้า stack ไม่ว่าง) หรือ height[x] * i (ถ้าว่าง)
• หลังวนจบ ให้ pop stack ที่เหลือคำนวณพื้นที่คล้ายกัน

ตัวอย่างโค้ด

class Solution(object):
    def largestRectangleArea(self, heights):
        stack = []
        i = 0
        ans = 0
        while i < len(heights):
            if len(stack) == 0 or heights[stack[-1]] <= heights[i]:
                stack.append(i)
                i += 1
            else:
                x = stack[-1]
                stack.pop()
                height = heights[x]
                temp = height * (i - stack[-1] - 1) if len(stack) != 0 else height * i
                ans = max(ans, temp)
        while len(stack) > 0:
            x = stack[-1]
            height = heights[x]
            stack.pop()
            temp = height * (len(heights) - stack[-1] - 1) if len(stack) != 0 else height * len(heights)
            ans = max(ans, temp)
        return ans

ob = Solution()
print(ob.largestRectangleArea([2,1,5,7,3,2]))

อินพุต

[2,1,5,7,3,2]

เอาต์พุต

12