प्रोग्राम यह पता लगाने के लिए कि हम पायथन में कुल कितनी बारिश पकड़ सकते हैं

मान लीजिए कि हमारे पास n गैर-ऋणात्मक पूर्णांकों की एक सरणी है। ये उस ऊंचाई का प्रतिनिधित्व कर रहे हैं जहां प्रत्येक बार की चौड़ाई 1 है, हमें गणना करनी होगी कि बारिश के बाद यह कितना पानी पकड़ने में सक्षम है। तो नक्शा इस तरह होगा -

यहां हम देख सकते हैं कि 8 नीले बॉक्स हैं, इसलिए आउटपुट 8 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

एक स्टैक सेंट, पानी परिभाषित करें:=0 और मैं:=0
जबकि मैं <ऊंचाई का आकार
- यदि स्टैक खाली है या ऊँचाई [स्टैक टॉप]> =ऊँचाई [i] है, तो i को स्टैक में पुश करें, i को 1 से बढ़ाएँ
- अन्यथा
  - x :=स्टैक टॉप एलिमेंट, स्टैक से टॉप डिलीट करें
  - अगर स्टैक खाली नहीं है, तो
    - अस्थायी:=न्यूनतम ऊंचाई [स्टैक टॉप एलिमेंट] और ऊंचाई [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]