Mô phỏng thuật toán Hứng nước mưa

Trapping Rain Water · Nhóm: Hai con trỏ

Hứng nước mưa bằng hai con trỏ: đi từ hai đầu vào giữa, luôn xử lý phía THẤP hơn vì phía đó mới là nút cổ chai chặn nước.

Ý tưởng

L ở đầu, R ở cuối; giữ leftMax và rightMax là chiều cao lớn nhất đã gặp bên trái, bên phải.

Nếu h[L] < h[R] thì cập nhật leftMax và cộng leftMax − h[L] vào tổng rồi L tiến; ngược lại làm tương tự với rightMax và R lùi.

Vì sao đúng

Nước trên một cột bị chặn bởi min của hai bức tường cao nhất hai phía; khi h[L] < h[R] thì rightMax chắc chắn ≥ h[R] > h[L], nên leftMax đã đủ quyết định lượng nước tại L.

Mã Python

def trap(h):
    L, R = 0, len(h) - 1
    left_max = right_max = 0
    water = 0
    while L < R:
        if h[L] < h[R]:
            left_max = max(left_max, h[L])
            water += left_max - h[L]
            L += 1
        else:
            right_max = max(right_max, h[R])
            water += right_max - h[R]
            R -= 1
    return water

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