पायथन में हम कितना कुल वर्षा जल पकड़ सकते हैं यह खोजने का प्रोग्राम

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

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

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

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