ดักน้ำฝนใน Python

สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มไม่เป็นลบจำนวน n ตัว เหล่านี้แสดงแผนที่ระดับความสูงที่ความกว้างของแต่ละแท่งเป็น 1 เราต้องคำนวณว่าน้ำสามารถดักจับหลังจากฝนตกได้มากน้อยเพียงใด ดังนั้นแผนที่จะเป็นแบบ −

ในที่นี้เราจะเห็นว่ามีกล่องสีน้ำเงิน 6 กล่อง ดังนั้นผลลัพธ์จะเป็น 6

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนด stack st, water :=0 and i :=0

• ในขณะที่ฉัน <ขนาดความสูง

  • ถ้าสแต็กว่างเปล่าหรือ height[stack top]>=height[i] จากนั้นกด i ลงใน stack ให้เพิ่ม i ขึ้น 1

  • อย่างอื่น

    • x :=stack top element ลบ top ออกจาก stack

    • ถ้าสแต็กไม่ว่างเปล่า

      • temp :=นาทีของความสูง[stack องค์ประกอบบนสุด] และความสูง[i]

      • dest :=i – stack top element – ​​1

      • น้ำ :=น้ำ + dist * (อุณหภูมิ – ความสูง[x])

• คืนน้ำ

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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]))

อินพุต

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

ผลลัพธ์

6