跳到主要内容

42. 接雨水(Hard)

题目描述​

给出一个数字代表柱子的高度，求出按此排列下，下雨之后能接多少水。

样例​

img

Input：height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output：6

题目解析​

使用单调栈去解决，如 [1, 0, 2] 中，2 不符合单调栈的情形，可以开始计算接雨水的面积。其中，1 和 2 分别是柱子的两端，根据木桶原理，使用 min(左柱高，右柱高) - 底高 可以计算出水池底高度。

  • 水池高：$min(H_左柱 - H_右柱) - H_底$
  • 水池宽：$I_{右} - I_{左} - 1$
  • 面积：$res = res + PoolHeight \times PoolWidth$

代理​

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        res = 0
        for cur in range(len(height)):
            while stack and height[stack[-1]] < height[cur]:
                pool_bottom = stack.pop()
                if not stack: break # 这里需要注意，当左边没有柱子的时候，就不用进行下面的计算了
                pool_width = cur - stack[-1] - 1
                pool_height = min(height[cur], height[stack[-1]]) - height[pool_bottom]
                res += pool_width * pool_height
            stack.append(cur)
        return res