42. 接雨水

Difficulty
Hard
Tags
单调栈
动态规划
URL
https://leetcode-cn.com/problems/trapping-rain-water/
Star
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
notion imagenotion image
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 
表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

单调栈

思路
维护一个递减栈，遍历数组，当当前元素大于栈顶时，说明可能可以储水。然后此时，当前元素就是右墙壁，此时栈顶即为湖底，将栈顶弹出来，如果栈中还有元素，说明可以储水。此时性的栈顶即为左墙壁。让后计算一下当前储水量即可
题解
class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        res = 0
        for i in range(0, len(height)):
            while stack and height[i] > height[stack[-1]]:
                pre = stack.pop() # 这是湖底
                if len(stack) == 0:
                    break # 这里没必要break的，只有不break才能形成一个递减栈，不然栈前面会多一个递增的栈
                Height = min(height[stack[-1]], height[i]) - height[pre]
                res += Height * (i-stack[-1]-1)
            stack.append(i)
        return res

#------------------#
class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) <= 1:
            return 0

        res, stack = 0, []
        for i in range(0, len(height)):
            # 维持一个 递减的栈，当发现比栈顶的大时，可以计算面积了
            while stack and height[i] > height[stack[-1]]:
                rightH = height[i]
                bottom = height[stack.pop()]
                if stack: # 如果还有左墙壁说明可以计算面积
                    leftH = height[stack[-1]]
                    width = i - stack[-1] - 1
                    res += (min(leftH, rightH)-bottom) * width
                    
            stack.append(i)
        return res

动态规划

思路
左边一束光打过去，右边一束光打过来，然后计算每个位置光最低的位置，再减去墙壁本身高度，就是当前位置可以储水的量
对每一个位置，都寻找从当前位置出发，向左，及向右看的最高值，然后两个最高值就分别为以当前位置为底的的左右墙，然后计算一下出水的面积
题解
class Solution:
    def trap(self, height: List[int]) -> int:
        res = 0
        left = [h for h in height]
        right = [h for h in height]
        for i in range(1, len(height)):
            left[i] = max(left[i-1], height[i])
        for j in range(len(height)-2, -1, -1):
            right[j] = max(right[j+1], height[j])

        for i in range(0, len(height)):
            res += min(left[i], right[i]) - height[i]

        return res

# 可以将三重循环压缩为两层循环
class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) <= 1:
            return 0

        res = 0

        left = [0] * len(height)
        left[0] = height[0]
        for i in range(1, len(height)):
            left[i] = max(left[i-1], height[i])

        right = [0] * len(height)
        right[-1] = height[-1]
        for j in range(len(height)-2, -1, -1):
            right[j] = max(right[j+1], height[j])
            res += min(left[j], right[j]) - height[j]
            

        return res