42.接雨水 python3

题目：

解析：

这道题有两类解法，横向和纵向。

• 纵向：只需要求解左边的最高值和右边的最高值，两者中较小的一个减去当前的高度，即为当前格子纵向的雨水量。
• 横向：如果当前的格子高度大于前一个，小于前面第二个，则可以确定前一个的一段横向的积水量。

代码：

class Solution:
    def trap(self, height: List[int]) -> int:
        
        stack = []
        rain = 0
        
        for i in range(len(height)):
            while len(stack) >= 2 and height[stack[-1]] < height[i]:
                rain = rain + (min(height[stack[-2]], height[i]) - height[stack[-1]]) * (i - stack[-2] - 1)
                stack.pop()
                
            if len(stack) == 1 and height[i] > height[stack[-1]]:
                stack.pop()
                
            stack.append(i)
        
        return rain

小结：

栈是一种思想，而不仅仅是一种数据结构。