পাইথনে রেইন ওয়াটার ট্র্যাপিং

ধরুন n সংখ্যক নন-নেগেটিভ পূর্ণসংখ্যার একটি অ্যারে আছে। এগুলো একটি এলিভেশন ম্যাপ প্রতিনিধিত্ব করে যেখানে প্রতিটি বারের প্রস্থ ১। বৃষ্টিপাতের পর কত পানি জমা হতে পারে তা গণনা করতে হবে।

এখানে ৬টি ব্লু বক্স দেখা যায়, তাই আউটপুট ৬।

সমাধানের ধাপগুলো −

স্ট্যাক st, water := 0, i := 0 সংজ্ঞায়িত করুন
while i < len(height) − যদি স্ট্যাক খালি থাকে অথবা height[stack[-1]] >= height[i] তবে stack.append(i); i++
অন্যথায় − x = stack.pop(); যদি স্ট্যাক খালি না হয় তবে temp = min(height[stack[-1]], height[i]); dist = i - stack[-1] - 1; water += dist * (temp - height[x])
water রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন −

class Solution(object):
    def trap(self, height):
        stack = []
        water = 0
        i=0
        while i=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]