Chương trình tìm tổng lượng mưa mà chúng ta có thể hứng được bằng Python

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

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

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

• Xác định một ngăn xếp, nước:=0 và i:=0
• while 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])

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

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([2,5,2,0,5,8,8]))

Đầu vào

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

Đầu ra

8