LeetCode解题报告(42)--柱状图的储水量

发表于 标签

原题如下 >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. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. 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!

从题目给出的图可以比较清楚知道，题目给出的数组中的每个数字代表一根柱子的高度，将数组中的数字全部表示为特定高度的柱子后，求这些柱子组成的容器能够容纳的水量。

解题思路：可以分别求出每根柱子的储水量，然后将每根柱子的储水量加起来即为总的储水量。而每根柱子的储水量可以通过下面方法求：找到这根柱子左边所有柱子中最高的那根，记为A；找到这根柱子右边所有柱子中最高的那根，记为B；min(A,B)-r即为这根柱子的储水量，r为这根柱子的高度。

实现代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if len(height)==0:
            return 0
        
        leftMax = []
        # leftMax Array
        max = height[0]
        for i in range(len(height)):
            if height[i] > max :
                max = height[i]
            leftMax.append(max)
        
        sum = 0
        rightMax = height[len(height)-1]
        for i in reversed(range(1,len(height)-1)):
            miniHeight = min(leftMax[i-1],rightMax)
            if miniHeight > height[i]:
                sum += miniHeight - height[i]

            if height[i] > rightMax:
                rightMax = height[i]
        return sum