Mô phỏng thuật toán Hình chữ nhật lớn nhất trong biểu đồ

Largest Rectangle in Histogram · Nhóm: Ngăn xếp & Hàng đợi

Tìm hình chữ nhật có diện tích lớn nhất khớp bên trong biểu đồ cột bằng ngăn xếp đơn điệu tăng lưu chỉ số cột.

Ý tưởng

Duyệt từng cột, giữ trong ngăn xếp các chỉ số cột có chiều cao tăng dần từ đáy lên đỉnh.

Gặp cột thấp hơn đỉnh thì pop đỉnh ra, coi nó là chiều cao thấp nhất và tính diện tích với bề rộng trải tới cột hiện tại.

Thêm cột ảo cao 0 ở cuối để xả sạch ngăn xếp, cập nhật diện tích lớn nhất.

Vì sao đúng

Mỗi cột chỉ có thể là cột thấp nhất của một hình chữ nhật, ngăn xếp đơn điệu cho biết ngay bề rộng tối đa của nó nên chỉ cần một lượt duyệt.

Mã Python

def largest_rectangle(h):
    stack = []            # indices, heights increasing
    best = 0
    for i in range(len(h) + 1):
        cur = h[i] if i < len(h) else 0
        while stack and h[stack[-1]] > cur:
            top = stack.pop()
            left = stack[-1] if stack else -1
            width = i - left - 1
            best = max(best, h[top] * width)
        stack.append(i)
    return best

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.