Bẫy nước mưa bằng Python

Giả sử chúng ta có một mảng gồm n số nguyên không âm. Chúng thể hiện một bản đồ độ cao trong đó chiều rộng của mỗi thanh là 1, chúng ta phải tính toán lượng nước mà nó có thể đọng lại sau khi mưa. Vì vậy, bản đồ sẽ như thế -

Ở đây chúng ta có thể thấy có 6 ô màu xanh, vì vậy đầu ra sẽ là 6.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định st stack, water:=0 và i:=0

• trong khi tôi

  • nếu là ngăn xếp trống hoặc chiều cao [đỉnh ngăn xếp]> =chiều cao [i], thì đẩy i vào ngăn xếp, tăng i lên 1

  • nếu không thì

    • x:=phần tử trên cùng của ngăn xếp, xóa phần trên khỏi ngăn xếp

    • nếu ngăn xếp không trống, thì

      • temp:=min of height [phần tử trên cùng của ngăn xếp] và height [i]

      • dest:=i - phần tử trên cùng của ngăn xếp - 1

      • water:=water + dist * (temp - height [x])

• trả lại nước

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

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