Chương trình tính lượng nước mưa có thể chứa được bằng Python

Cho mảng height chứa các số nguyên không âm đại diện cho độ cao các cột (rộng 1). Tính lượng nước mưa có thể chứa được giữa các cột.

Ví dụ: [2,5,2,0,5,8,8] → 8 (8 ô vuông màu xanh trong hình minh họa).

Quy trình giải quyết (Sử dụng Stack)

1. Khởi tạo ngăn xếp stack, water = 0, i = 0.
2. Trong khi i < len(height):
   • Nếu stack rỗng hoặc height[stack[-1]] >= height[i]: đẩy i vào stack, tăng i.
   • Ngược lại:
     • Lấy x = stack.pop().
     • Nếu stack không rỗng: tính temp = min(height[stack[-1]], height[i]), dist = i - stack[-1] - 1, cộng dist * (temp - height[x]) vào water.
3. Trả về water.

Ví dụ mã nguồn

class Solution:
    def trap(self, height):
        stack = []
        water = 0
        i = 0
        while i < len(height):
            if not stack or height[stack[-1]] >= height[i]:
                stack.append(i)
                i += 1
            else:
                x = stack.pop()
                if stack:
                    temp = min(height[stack[-1]], height[i])
                    dist = i - stack[-1] - 1
                    water += dist * (temp - height[x])
        return water

ob = Solution()
print(ob.trap([2, 5, 2, 0, 5, 8, 8]))  # Output: 8

Đầu vào

[2, 5, 2, 0, 5, 8, 8]

Đầu ra

8