算法题--求蓄水池的蓄水量

image.png

0. 链接

题目链接

1. 题目

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

image.png

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

2. 思路：动态规划

2.1 先从左到右计算截止到目前位置的最大值(作用是以左边作为参考依据，水坑全部填平)
2.2 再从右到左计算截止到目前为止的最大值(作用是以右边作为参考依据，水坑全部填平)
2.3 由于前两步得到的意见都是片面的，存在的主要问题是只考虑了一边作为参照物，没考虑另一半的开区间存不住水的问题; 所以这一步需要修正边界处的问题：方法是在每个位置，取两者得到结果的较小值，即为水池填充后的真实值，再减去原始数组的值，即得到填充的总水量

3. 代码

class Solution1:
    def trap(self, height: List[int]) -> int:
        length = len(height)
        left_max = [height[0]]
        right_max = [height[length - 1]]

        for i in range(1, length):
            left_max.append(max(left_max[i - 1], height[i]))

        for i in range(length - 2, -1, -1):
            right_max.append(max(right_max[length - 2 - i], height[i]))

        rtn = 0
        for i in range(length):
            rtn += min(left_max[i], right_max[length - 1 - i]) - height[i]

        return rtn

solution = Solution1()
print(solution.trap([0,1,0,2,1,0,1,3,2,1,2,1]))
print(solution.trap([2,1,0,2]))

输出结果

6
3

4. 结果

image.png