মান ল করুন n সংখ্যক নন-নেগেটিভ ইন্টিজারের একটি অ্যারে। এগুলো উচ্চতা বোঝায় যেখানে প্রতিটি বারের প্রস্থ ১। বৃষ্টিপাতের পর কতটুকু পানি জমা রাখা যায় তা গণনা করতে হবে। ম্যাপটি এমন হবে:
এখানে ৮টি নীল বক্স দেখা যাচ্ছে, তাই আউটপুট হবে ৮।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:
- একটি স্ট্যাক st, water := 0 এবং i := 0 সংজ্ঞায়িত করুন
- যখন i < height-এর আকার:
- যদি স্ট্যাক খালি থাকে বা height[stack top] >= height[i], তবে i কে স্ট্যাকে পুশ করুন, i ১ বাড়ান
- অন্যথায়:
- x := stack top এলিমেন্ট, স্ট্যাক থেকে টপ মুছে ফেলুন
- যদি স্ট্যাক খালি না থাকে, তবে:
- temp := min(height[stack top], height[i])
- dest := i - stack top - 1
- water := water + dist * (temp - height[x])
- water ফেরত দিন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:
উদাহরণ
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
