পাইথনে বৃষ্টির পানি আটকানো

ধরুন আমাদের n অ-নেতিবাচক পূর্ণসংখ্যার একটি অ্যারে আছে। এগুলি একটি উচ্চতার মানচিত্র উপস্থাপন করছে যেখানে প্রতিটি বারের প্রস্থ 1, আমাদের গণনা করতে হবে বৃষ্টির পরে এটি কতটা জল আটকাতে সক্ষম। সুতরাং মানচিত্রটি −

এর মত হবে

এখানে আমরা দেখতে পাচ্ছি 6 টি নীল বাক্স আছে, তাই আউটপুট হবে 6।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি স্ট্যাক st, water :=0 এবং i :=0
সংজ্ঞায়িত করুন
যখন আমি <উচ্চতার আকার
- যদি স্ট্যাকটি খালি হয় বা উচ্চতা [স্ট্যাক টপ]>=উচ্চতা[i] হয়, তাহলে আইকে স্ট্যাকের মধ্যে পুশ করুন, i 1 দ্বারা বাড়ান
- অন্যথায়
  - x :=স্ট্যাক শীর্ষ উপাদান, স্ট্যাক থেকে শীর্ষ মুছে দিন
  - যদি স্ট্যাক খালি না হয়, তাহলে
    - temp :=উচ্চতার মিনিট [স্ট্যাক টপ এলিমেন্ট] এবং উচ্চতা[i]
    - dest :=i – স্ট্যাক টপ এলিমেন্ট – 1
    - জল :=জল + দূরত্ব * (তাপ – উচ্চতা[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]