Giữ nước mưa trong Python

Cho mảng n số nguyên không âm biểu diễn bản đồ độ cao (mỗi cột rộng 1). Tính lượng nước có thể giữ lại sau mưa.

Kết quả ví dụ: 6 đơn vị nước.

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

• Stack lưu chỉ số các cột giảm dần chiều cao
• Duyệt i: nếu stack rỗng hoặc height[stack[-1]] >= height[i], push i
• Ngược lại: pop x, nếu stack không rỗng: tính nước giữa stack[-1] và i
• water += (i - stack[-1] - 1) * (min(height[stack[-1]], height[i]) - height[x])

Ví dụ

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

ob = Solution()
print(ob.trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

Đầu vào

[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Đầu ra

6