Chương trình tìm diện tích hình chữ nhật lớn nhất dưới biểu đồ histogram bằng Python

Giả sử chúng ta có một danh sách các số đại diện cho chiều cao các cột trong biểu đồ histogram. Nhiệm vụ là tìm diện tích hình chữ nhật lớn nhất có thể hình thành dưới các cột.

Ví dụ, nếu đầu vào là nums = [3, 2, 5, 7], kết quả đầu ra sẽ là 10.

Giải thuật

Sử dụng ngăn xếp (stack) để giải quyết hiệu quả:

• Khởi tạo ngăn xếp stk = [-1].
• Thêm 0 vào cuối mảng heights.
• Khởi tạo ans = 0.
• Duyệt qua từng chỉ số i từ 0 đến độ dài heights:
  • Trong khi heights[i] < heights[stk[-1]]:
    • Lấy chiều cao h = heights[stk.pop()].
    • Tính chiều rộng w = i - stk[-1] - 1.
    • Cập nhật ans = max(ans, h * w).
  • Đẩy i vào ngăn xếp.
• Trả về ans.

Ví dụ minh họa

class Solution:
    def solve(self, heights):
        stk = [-1]
        heights.append(0)
        ans = 0
        for i in range(len(heights)):
            while heights[i] < heights[stk[-1]]:
                h = heights[stk.pop()]
                w = i - stk[-1] - 1
                ans = max(ans, h * w)
            stk.append(i)
        return ans

ob = Solution()
nums = [3, 2, 5, 7]
print(ob.solve(nums))

Đầu vào

[3, 2, 5, 7]

Đầu ra

10