โปรแกรมหาปริมาณน้ำฝนที่เก็บได้ใน Python

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

ตัวอย่าง: [2,5,2,0,5,8,8] สามารถเก็บน้ำได้ 8 หน่วย (เห็นจากกราฟ)

ขั้นตอนการแก้ปัญหา (ใช้ Stack)

1. สร้างสแต็ก stack, water = 0, i = 0
2. วนลูป while i < len(height):
   • ถ้า stack ว่าง หรือ height[stack[-1]] >= height[i]:
     • เพิ่ม i เข้า stack, เพิ่ม i ขึ้น 1
   • อื่นๆ:
     • x = stack[-1], นำ stack.pop() ออก
     • ถ้า stack ไม่ว่าง:
       • temp = min(height[stack[-1]], height[i])
       • dist = i - stack[-1] - 1
       • water += dist * (temp - height[x])
3. คืนค่า water

ตัวอย่างโค้ด Python

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]))  # Output: 8

อินพุต / เอาต์พุต

Input: [2,5,2,0,5,8,8]

Output: 8