如何在陷阱雨水问题中实现堆栈，而不是像下面所示以迭代方式解决它？

Question

我正在解决Gfg的雨水收集问题。

我的方法是：对于任何索引，我都会在右侧数组中找到最大元素，在左侧数组中找到最大元素。然后，对于相应的位置，我将找到截留在那里的水，并使用公式将其存储在水中[]，公式为：水[I]=最小值（maxL[I]，MaxR[I]）-数组[I]。（请参阅代码以了解更多信息）

最后，我将返回水中所有元素的总和[]。

代码：

class Solution:
    def trappingWater(self, arr,n):
        maxL=[]    #for storing the maximum on left
        maxR=[]    #for storing the maximum on right
        water=[0]*n
        for i in range(len(arr)):
            if len(maxL)==0:
                mx=arr[i]
            elif arr[i]>mx:
                mx=arr[i]
            maxL.append(mx)
        for i in range(len(arr)-1,-1,-1):
            if len(maxR)==0:
                mx=arr[i]
            elif arr[i]>mx:
                mx=arr[i]
            maxR.append(mx)
        maxR=maxR[::-1]
        
        for i in range(n):
            water[i]=min(maxL[i],maxR[i])-arr[i]
        return sum(water)

但由于这是一个来自堆栈主题的问题，我想知道如何在这个问题中实现堆栈来解决这个问题。

Answer 1

你的方法很好。

只要砌块高度降低，就可以使用堆垛来收集砌块，因为它们可以用作左侧支撑以保持水分。

与您的解决方案相反，然后通过两个（可能较远的）区块之间的水平“跨度”来添加水量。为此，还需要将块的x坐标放置在堆栈上。

当一个条目的高度不大于我们当前访问的块的高度时，它将从堆栈中删除。在这种情况下，需要将一些水量添加到总量中：从堆栈中弹出较低的块，并计算该块上方的水量，介于现在位于堆栈顶部的块（如果有）和当前块之间的左支撑。

下面是脚本中的内容：

class Solution:
    def trappingWater(self, arr, n):
        stack = []
        water = 0
    
        for x, y in enumerate(arr):
            while len(stack) > 0 and stack[-1][1] <= y:
                x1, y1 = stack.pop()  # we will look for water above this block
                if stack:
                    x2, y2 = stack[-1]  # this is the left-sided support for holding water
                    water += (min(y2, y) - y1) * (x - x2 - 1)
            stack.append((x, y))
        return water