পাইথনে আমরা মোট কত পরিমাণ বৃষ্টি ধরতে পারি তা খুঁজে বের করার প্রোগ্রাম

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

এর মত হবে

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

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

একটি স্ট্যাক 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([2,5,2,0,5,8,8]))

ইনপুট

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