如何在 Trapping Rain Water Problem 中实现堆栈而不是如下所示以迭代方式解决它？

Question

我正在从 Gfg 解决 Trapping Rain Water Problem。

我的方法：对于任何索引，我都会在右侧数组中找到最大元素，在左侧数组中找到最大元素。然后对于相应的位置，我将找到被困在那里的水，并使用以下公式将其存储在 Water[] 中： water[i]=min(maxL[i],MaxR[i])-array[i] .（请参阅代码以获得更清晰的信息）

最后我会returnWater[]中所有元素的总和。

代码：

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)

但由于这是stack topic的问题，我想知道如何在这个问题中实现stack来解决这个问题。

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

如何在 Trapping Rain Water Problem 中实现堆栈而不是如下所示以迭代方式解决它？

How to implement stack in the Trapping Rain Water Problem rather than solving it in iterative way as shown below?

python

algorithm

data-structures

stack