โปรแกรมหาจำนวนฝนที่เราตกได้ใน Python

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

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

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

• กำหนดสแต็ก st, น้ำ :=0 และ i :=0
• ในขณะที่ฉัน <ขนาดความสูง
  • ถ้า stack ว่างเปล่าหรือ height[stack top]>=height[i] จากนั้นดัน i เข้าไปใน stack เพิ่ม i ขึ้น 1
  • อย่างอื่น
    • x :=stack top element ลบ top จาก stack
    • ถ้า stack ไม่ว่างก็
      • temp :=นาทีของความสูง[stack top element] และ height[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([2,5,2,0,5,8,8]))

อินพุต

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

ผลลัพธ์

8