Hình chữ nhật lớn nhất trong biểu đồ cột trong Python

Cho mảng số nguyên biểu diễn chiều cao các cột trong biểu đồ (histogram), mỗi cột rộng 1 đơn vị. Tìm diện tích hình chữ nhật lớn nhất.

Các bước giải quyết (Monotonic Stack O(n)):

• Stack lưu chỉ số các cột tăng dần chiều cao
• Duyệt i từ 0 đến n-1: nếu stack rỗng hoặc height[stack[-1]] <= height[i], push i
• Ngược lại: pop x = stack[-1], tính diện tích với height[x] làm chiều cao, chiều rộng = i - stack[-1] - 1 (hoặc i nếu stack rỗng)
• Sau vòng lặp, xử lý các phần tử còn lại trong stack

Ví dụ

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]))

Đầu vào

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

Đầu ra

12